[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）
此时慢指针的下一个节点是后半段链表的头，也将是新链表的头节点
断开两段链表并重新相连，让慢指针指向空指针，快指针指向头节点
返回新的头节点

/**
 * 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