LeetCode 61. 旋转链表

原题链接

难度：$middle$

题目描述

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

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
复制示例输入

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]
复制示例输入

提示：

• 链表中节点的数目在范围 $[0,500]$ 内
• $-100<=Node.val<=100$
• $0<=k<=2\ast 10^9$

---

算法

(模拟，连接) $O(n)$

• 这道题中 k 可能很大，所以我们令 k=k%n，n是链表长度。
• 创建两个指针 first, second，分别指向头结点，先让 first 向后移动 k个位置，然后first和second同时向后移动，直到first走到链表最后一个元素。
• 此时first指向链表末尾，second指向分界点。然后我们把链表从分界点处断开，然后把后半段接在前半段前面即可。

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 %= n;if (k == 0) return head;ListNode* first = head;while(k -- && first != NULL) first = first->next;ListNode* second = head;while (first->next) {first = first->next;second = second->next;}first->next = head;head = second->next;second->next = 0;return head;}
};