61. 旋转链表

题目描述

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

示例 1：

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

示例 2：

1 2	`输入：head = [0,1,2], k = 4 输出：[2,0,1]`

提示：

链表中节点的数目在范围 \([0, 500]\) 内
\(-100 \le Node.val \le 100\)
\(0 \le k \le 2 * 10^9\)

算法与思路

首先我们需要处理\(k\)，使\(k=k \bmod n\)，其中 \(n\) 为链表内节点个数。

创建两个指针 \(first\) 和 \(second\)，分别指向头节点。先让 \(first\) 向后移动 \(k\) 次，然后 \(first\) 和 \(second\) 同时向后移动，直到 \(first\) 移动到链表末尾。

此时 \(first\) 指向链表末尾，而 \(second\) 指向分界点，我们需要把链表从分界点断开，把后半段接在前半段即可。

时间复杂度：总共遍历两次链表，时间复杂度为 \(O(n)\)。

代码

C++

/**
 * 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) return head;
        int n = 0;
        ListNode* p = head;
        while (p) {
            n++;
            p = p->next;
        }

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

        ListNode* first = head;
        while (k-- && first) first = first->next;
        ListNode* second = head;
        while (first->next) {
            second = second->next;
            first = first->next;
        }

        first->next = head;
        head = second->next;
        second->next = nullptr;
        return head;
    }
};