刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/rotate-list/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

思路

其实这道题还是挺简单的

• 所谓的旋转其实就是找到一个位置，成环+拆链
• 算出链长后，就可以计算得出需要右移的步数，也就是明白了成环之后在何处拆链
• 使用快慢指针，移动到拆链位置
• 执行成环+拆链

思路还是挺简单的，细节在注释~

代码

func rotateRight(head *ListNode, k int) *ListNode {
	// fail fast
	if head == nil {
		return head
	}
	
	// 统计链表长度
	fast := head
	listLen := 0
	for fast != nil {
		fast = fast.Next
		listLen++
	}

	// 计算需要右移步数
	stepNum := k % listLen
	// 余数为0则无需移动，直接返回
	if stepNum == 0 {
		return head
	}

	// 快慢指针法，找到需要拆链的位置
	fast, slow := head, head
	for ; stepNum > 0; stepNum-- {
		fast = fast.Next
	}
	// 让slow指向需要拆开的两个节点中的前一个
	// 也就是新的链尾
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}

	// 先将首尾相连
	fast.Next = head
	// 记录新的链头
	newHead := slow.Next
	// 拆链形成新的链
	slow.Next = nil
	return newHead
}