小白试水——leetcode腾讯题库

腾讯题库"/>

小白试水——leetcode腾讯题库

题目61：旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL

解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL

解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

方法 1：

直觉

链表中的点已经相连，一次旋转操作意味着：

先将链表闭合成环
找到相应的位置断开这个环，确定新的链表头和链表尾

新的链表头在哪里？

在位置 n-k 处，其中 n 是链表中点的个数，新的链表尾就在头的前面，位于位置 n-k-1。

我们这里假设 k < n

如果 k >= n 怎么处理？

k 可以被写成 k = (k // n) * n + k % n 两者加和的形式，其中前面的部分不影响最终的结果，因此只需要考虑 k%n 的部分，这个值一定比 n 小。

算法

算法实现很直接：

找到旧的尾部并将其与链表头相连 old_tail.next = head，整个链表闭合成环，同时计算出链表的长度 n。
找到新的尾部，第 (n - k % n - 1) 个节点 ，新的链表头是第 (n - k % n) 个节点。
断开环 new_tail.next = None，并返回新的链表头 new_head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""# 特殊情况if not head or not head.next or not k:return head# 形成闭环链表old_tail = headn = 1while old_tail.next:old_tail = old_tail.nextn += 1old_tail.next = head# 找到新的链尾和链头位置new_tail = headfor i in range(n - k % n - 1):new_tail = new_tail.nextnew_head = new_tail.next# 断开链表闭环new_tail.next = Nonereturn new_head

这道题难点，就是如何找到那个旋转点？

比如示例1：1->2->3->4->5->NULL， k = 2 ,我们要找到3这个值，只要把它下一位为空，将下面一段链表和它这段链表连接起来就行了！

按照题目的意思是向右移动2位，换句话说，以3作为链表头，把它前面的链表连在它后面!现在问题就是如何找3，我们发现链表的个数-k就是从链表头到3位置。

还有一个问题，就是如果 k = 6 其实就是相等于 k=1；所以我们要防止循环。

最终就成为：

1. 求链表长度
2. 找 n - n % k 的位置

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def rotateRight(self, head, k):if not head or not head.next:return head# 链表个数n = 0p = headwhile p:n += 1p = p.nextk = n - k % np = head# 找前一段链表while k > 1:p = p.nextk -= 1head1 = p.nextif not head1:return head#前一段链表最后至空p.next = Nonep = head1# 后一段链表和前一段链表连接起来while p.next:p = p.nextp.next = headreturn head1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def rotateRight(self, head,k):if not head or not head.next or not k:return headn = 0l = ListNode(0)l.next = headp1 = lp2 = l# 计算个数while p1.next:n += 1p1 = p1.next#print(n)# 找前一段链表k = n - k % n#print(k)while k :p2 = p2.nextk -= 1# 连接p1.next = l.nextl.next = p2.nextp2.next = Nonereturn l.next

学习代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def rotateRight(self, head: ListNode, k: int) -> ListNode:l = []while head: l[len(l):], head = [head], head.nextif l: l[-1].next, l[-1 - k % len(l)].next = l[0], Nonereturn l[- k % len(l)] if l else None