61. 旋转链表

🟠   🔖  链表 双指针  🔗 力扣 LeetCode

题目

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2

Output: [4,5,1,2,3]

Example 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

题目大意

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

解题思路

这道题需要注意的点是，k 可能很大，如 k = 2000000000 ，如果是循环肯定会超时。应该找出 O(n) 的复杂度的算法才行。由于是循环旋转，最终状态其实是确定的，利用链表的长度取余可以得到链表的最终旋转结果。

• 使用 start 作为虚拟头节点，方便处理链表的连接和首节点；
• 计算链表的长度，并将 end 指针指向最末尾的节点；
• 将 k 对链表长度取余，避免重复操作；
• 将 prev 指向链表倒数第 k + 1 个节点，然后按照要求拼接链表，并返回结果；

代码

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
	if (!head || !head.next || k === 0) return head;

	let len = 1;
	let prev = head;
	let start = new ListNode(0, head);
	let end = head;

	// 计算链表的长度，并将end指向最末尾的节点
	while (end.next) {
		len++;
		end = end.next;
	}

	// k 对链表长度取余，避免重复操作
	k = k % len;

	// 将prev指向链表倒数第k + 1个节点
	for (let i = 0; i < len - k - 1; i++) {
		prev = prev.next;
	}

	// 按要求拼接链表
	end.next = head;
	start.next = prev.next;
	prev.next = null;
	return start.next;
};

相关题目

题号	标题	题解	标签	难度
189	轮转数组	[✓]	数组 数学 双指针
725	分隔链表		链表