XTAO's Tech Blog
0%

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

发表于 更新于 分类于 ， 评论数：
1.4k 1 分钟

题目描述

题目链接：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

推荐文章