【LeetCode】61. 旋转链表

1 问题

给你一个链表的头节点 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]

2 答案

自己写的不对

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        l = 0
        dunny = ListNode(0)
        dunny.next = head
        while head:
            head = head.next
            l += 1

        if k % l == 0:
            return head
        for _ in range(k % l):
            while head:
                if head.next == None:
                    head.next = dunny.next
                    break
                head = head.next
        return dunny.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

官方解，使用快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next: return head
        l = 0  # 长度
        cur = head  # 要复制一份，不然求head的长度时，head就被遍历没了
        while cur:
            cur = cur.next
            l += 1
        k %= l
        if k == 0: return head
        fast, slow = head, head
        while k:  # 先让fast走k步
            fast = fast.next
            k -= 1
        while fast.next:  # 让fast走到倒数第一个节点，不让他走完
            fast = fast.next
            slow = slow.next
        newHead = slow.next  # slow的下一个节点是newHead的第一个节点
        slow.next = None  # 对slow后进行打断
        fast.next = head  # fast连接head的第一个节点
        return newHead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

步骤：

1. 求链表长度；
2. 找出倒数第 $k+1$ 个节点；
3. 链表重整：将链表的倒数第 $k+1$ 个节点和倒数第 $k$ 个节点断开，并把后半部分拼接到原链表的头部。新链表的起始节点就是原链表的倒数第 $k$ 个节点

https://leetcode.cn/problems/rotate-list/solutions/682429/fu-xue-ming-zhu-wen-ti-chai-fen-fen-xian-z4dr/