问题描述
LeetCode 61. 旋转链表 (opens in a new tab)，难度中等。
给你一个链表的头节点 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 <= 1000 <= k <= 2 * 109
题解
模拟
解题思路：具体看下方代码注释，大概思路如下：
- 获取链表长度，计算出目标链表
newHead的位置； - 然后将这两部分链表拆分并反过来拼接。
Solution.java
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
// 遍历获取数组长度并找到尾节点
ListNode temp = head;
int length = 1;
while (temp.next != null) {
length++;
temp = temp.next;
}
ListNode tail = temp;
// 移动次数先对链表长度取模，然后将指针移动到新链表的首节点上
// 例如：[1, 2, 3, 4, 5, 6] k = 2
// 移动两次，[3, 4, 5, 6, 1, 2] newHead = 3
// 则当前 head = 1 节点需要移动 4 次
// 我们需要找到 newHead 的前驱节点 2
k = length - k % length;
temp = head;
// temp 为 newHead 的前驱节点
for (int i = 0; i < k - 1; ++i) {
temp = temp.next;
}
ListNode newHead = temp.next != null ? temp.next : head;
// 判断 newHead 和 tail 节点是否同一节点
if (tail == newHead) {
newHead.next = head;
} else {
tail.next = head;
}
// newHead 前驱节点断尾
// 该代码必须写在最后，否则当链表长度只有 1 的时候提前断尾会出现死循环
temp.next = null;
return newHead;
}
}