61. 旋转链表

题目-中等难度

相关企业
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：*

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 快慢指针找到分割位置

时间
20ms
击败 81.37%使用 Python 的用户
内存
12.63mb
击败 83.54%使用 Python 的用户

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""# 先计算链表长度p = headl = 0while p:l += 1p = p.nextif l <= 1 or k == 0:return head# 快慢指针fast = slow= head# 让快指针先行k%l个位置for i in range(k%l):fast = fast.next# 然后让快指针行到最后节点位置，慢指针则是后半链表的头节点位置nn = ListNode(-1)cur = nnwhile fast:fast = fast.nextcur.next = ListNode(slow.val)slow = slow.nextcur = cur.next# 如果slow存在, 得到slow的最后一个节点位置, 拼接nnif slow:r = slowelse:return nn.nextwhile r and r.next:r = r.next# slow + 排除头节点的nnr.next = nn.nextreturn slow

2. 连成环后截断

时间
24ms
击败 53.42%使用 Python 的用户
内存
12.51mb
击败 97.52%使用 Python 的用户

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""p = head# 长度计算n = 1while p and p.next:n+=1p = p.next# 如果k为0 或者n小于等于1if(k == 0) or n <= 1:return head# nnt 获取截断位置nt = head# 成环p.next = head# 获取截断点for i in range(n - k % n - 1):nt = nt.next# 结果头res = nt.next# 截断循环nt.next = Nonereturn res