1. 题目

原题链接

给你一个链表的头节点 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 * 109

Related Topics 链表 双指针
👍 576 👎 0

2. 题解

2.1 解法1: 闭合为环

算法流程:
1.同解法1 先计算链表长度, 同时找到尾节点
2.将链表闭合为环, 然后只要找到新的头结点及其前驱结点断链即可, 其头结点为 从 head 开始的第 len-k-1 个结点

    class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null || k == 0) return head;int len = 1;ListNode p = head;while (p.next != null) {len++;p = p.next;}k = k % len;if (k == 0) return head;p.next = head;int index = len - k;p = head;while (index > 1) {index--;p = p.next;}ListNode newHead = p.next;p.next = null;return newHead;}}

参考: 官方题解

2.2 解法2: 转化为寻找倒数第 k 个结点

参考链接: 算法—LeetCode 剑指 Offer 22. 链表中倒数第k个节点

算法流程:

1. 因为 k 可能大于 n, 所以需要先求得链表长度 len, 用于取 k%len
2. 寻找到链表倒数第 k 个结点(使用快慢指针), 该节点即为 新的头结点

    class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null || k == 0) {return head;}// 1. 求链表长度ListNode p = head;int len = 0;while (p != null) {len++;p = p.next;}k = k % len;if (k == 0) {return head;}// 2. 寻找倒数第k个结点, 快慢指针, fast 先走 k 步, 然后 fast和 slow 一起走ListNode fast = head;ListNode slow = head;while (k > 0) {fast = fast.next;k--;}while (fast.next != null) {fast = fast.next;slow = slow.next;}// 此时 slow.next 为新的头结点ListNode newHead = slow.next;slow.next = null;fast.next = head;return newHead;}}

参考: 【负雪明烛】问题拆分，分享详细思路与代码注释