旋转链表（61）

题目

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL

解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL

算法

数组

转换为数组进行旋转，旋转后再生成链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const rotateRight = (head, k) => {
	const counts = [];
	while (head) {
		counts.push(head.val);
		head = head.next;
	}
	let rotateCount = k % counts.length;
	while (rotateCount--) {
		counts.unshift(counts.pop());
	}
	let rotatedList = new ListNode(),
		rotatedHead = rotatedList;
	for (let i = 0; i < counts.length; i++) {
		rotatedList.next = new ListNode(counts[i]);
		rotatedList = rotatedList.next;
	}
	return rotatedHead.next;
};

环形链表

将链表闭合成环，找到合适的位置再断开这个环，完成旋转：

• 首先要排除只有一个节点和没有节点的情况
• 将链表头部设置为originHead，先遍历链表，找到最后一个节点，求出链表的总长度（因为遍历到最后一个节点第n个节点，总共移动了n-1次，所以将length初始化为1）并将最后一个节点的next指向originHead
• 将末尾节点设置为endNode
• 然后首尾节点一起移动，可知向右旋转k次，等于首尾节点向前移动length-k次
• 然后将末尾节点endNode的下一个指向null，并返回originHead

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const rotateRight = (head, k) => {
	if (!head || !head.next) return head;
	let originHead = head,
		length = 1;
	while (head.next) {
		head = head.next;
		length++;
	}
	let endNode = head;
	endNode.next = originHead;
	let moveCount = length - (k % length);
	while (moveCount--) {
		originHead = originHead.next;
		endNode = endNode.next;
	}
	endNode.next = null;
	return originHead;
};