各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 62 天。今天力扣上的每日一题是「61. 旋转链表」。

解题思路

题意：将链表每个节点向右移动 k 个位置，相当于把链表的后面 k % len 个节点移到链表的最前面。（len 为 链表长度）

所以本题的步骤：

  1. 求链表长度；
    2. 找出倒数第 k+1 个节点；
    3. 链表重整：将链表从倒数第 k+1 个节点之后打断，并把后半部分拼接到链表的头部。

1. 求链表长度

求链表长度应该是链表最基本的题型了，直接用一个指针 cur ，开始时指向链表的头 head，一直向后移动到 cur 为空时，经历的链表节点数就是链表长度。

2. 找出倒数第 k+1 个节点

可以先在 剑指 Offer 22. 链表中倒数第k个节点 进行练习。

思路还是比较简单的：
1. 两个指针 slow 和 fast 值距离是 k，先让 fast 指向链表的第 k + 1 个节点，slow 指向第 1 个节点；
2. 然后 slow 和 fast 同时向后移动，当 fast 移动到链表的最后一个节点的时候，那么 slow 指向链表的倒数第 k + 1 个节点。

链表重整

重整操作也比较简单：
- newHead 是新链表的头部，它应该是原链表倒数第 k 个节点，即 slow.next；
- slow 需要跟 slow.next 断开；
- fast 是老链表的结尾，需要连接上老链表的开头。

代码如下：

  1. class Solution:
  2.     def rotateRight(self, head, k):
  3.         if not head or not head.next: return head
  4.         # 求链表长度
  5.         _len = 0
  6.         cur = head
  7.         while cur:
  8.             _len += 1
  9.             cur = cur.next
  10.         # 对长度取模
  11.         k %= _len
  12.         if k == 0: return head
  13.         # 让 fast 先向后走 k 步
  14.         fast, slow = head, head
  15.         while k:
  16.             fast = fast.next
  17.             k -= 1
  18.         # 此时 slow 和 fast 之间的距离是 k
  19.         # 当 fast.next 为空时，fast 指向链表最后一个节点，slow 指向倒数第 k + 1 个节点
  20.         while fast.next:
  21.             fast = fast.next
  22.             slow = slow.next
  23.         # newHead 是倒数第 k 个节点，即新链表的头
  24.         newHead = slow.next
  25.         # 让倒数第 k + 1 个节点 和 倒数第 k 个节点断开
  26.         slow.next = None
  27.         # 让最后一个节点指向原始链表的头
  28.         fast.next = head
  29.         return newHead

  • 时间复杂度：$O(N)$

  • 空间复杂度：$O(1)$

刷题心得

  • 今天这个题目基于找出链表的倒数第 K 个节点做了一点改进。
    - 链表问题，要舍得用变量，要在纸上画一画。

参考资料：负雪明烛

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！