61. 旋转链表#

题目#

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

3
示例 1：
4

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

8
示例 2:
9

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

13
提示：
14

15
链表中节点的数目在范围 [0, 500] 内
16
-100 <= Node.val <= 100
17
0 <= k <= 2 * 10^9

题目思路#

理清 len - 1 - k % len 即为尾节点，就能弄明白这道题。

题目代码#

代码块#

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* rotateRight(ListNode* head, int k) {
14
        if(k == 0 || head == NULL || head -> next == nullptr) return head;
15
        int len = 1;
16
        ListNode* fast = head;
17
        ListNode* slow = head;
18
        while(fast -> next != nullptr)
19
        {
20
            fast = fast -> next;
21
            ++len;
22
        }
23
        fast -> next = head;
24
        k = len - 1 - k % len; //此处注意移动k步后的末尾节点,鄙人在此卡了接近半小时
25
        if(k == len) return head;//最后想明白了len - 1是链表尾节点，k % len为剩余步数
26
        while(k)     //len - 1 - k % n为尾节点
27
        {
28
            slow = slow -> next;
29
            k--;
30
        }
31
        fast = slow -> next;
32
        slow -> next = nullptr;
33
        return fast;
34
    }
35
};

复杂度#

时间复杂度：O(n)，遍历两次链表
空间复杂度：O(1)，常数级