0%

[Leetcode]61. Rotate List(C++)

题目描述

题目链接:61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

例子

例子 1

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

例子 2

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

解题思路

链表版本的旋转问题,相较于数组简单一点,只需要找到断点,然后从中间断开链表,把后半段的尾节点连上前半段的头节点即可。大致思路:

  • 遍历一次求出链表长度,对 k 求余 (k 的数量级太大,如果不对链表长度求余很影响效率)
  • 快慢指针法,让快指针先遍历 k 步,然后快慢指针同步前进,这样快指针指向最后一个节点时(下一节点为空),慢指针刚好指向从后往前数第 k + 1 节点(快慢指针相差 k)
  • 此时慢指针的下一个节点是后半段链表的头,也将是新链表的头节点
  • 断开两段链表并重新相连,让慢指针指向空指针,快指针指向头节点
  • 返回新的头节点
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !k) return head;

ListNode* fast = head;
int len = 0;
while (fast) {
len++;
fast = fast->next;
}

k %= len;
if (!k) return head;

ListNode* slow = head;
fast = head;
int step = 0;
while (fast->next) {
if (step >= k) {
slow = slow->next;
}
fast = fast->next;
step++;
}
ListNode* new_head = slow->next;
slow->next = nullptr;
fast->next = head;

return new_head;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 61.RotateList.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions