Leetcode每日一题-61.旋转链表

题解看代码注释

方式一

不借助额外空间，对k取模，移动有限次 核心在于首尾相连+断链

代码

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil {
		return head
	}
	p := head
	// 节点总数
	size := 1
	for p.Next != nil {
		p = p.Next
		size++
	}
	// 得到最终要移动的次数
	k %= size
	// 链首尾相连
	p.Next = head
	// 记录当前的p: 最后一个位置
	last := p
	p = head
	// 移动值 k次
	for i := 0; i < k; i++ {
		cur := p.Val
		nextVal := p.Next.Val
		for j := 0; j < size; j++ {
			p.Next.Val = cur
			p = p.Next
			cur = nextVal
			nextVal = p.Next.Val
		}
	}
	// 断链
	last.Next = nil
	return head
}

运行结果

方式二

借助额外的切片存储所有的节点值，核心在于记录初始位置，可以直接得到移动k步后的值，性能理论上来说或许更快

代码

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil {
		return head
	}
	p := head
	// 存储各位置的初始节点
	vals := []int{p.Val}
	for p.Next != nil {
		p = p.Next
		vals = append(vals, p.Val)
	}
	// 得到最终要移动的次数
	k %= len(vals)
	p = head
	for i := 0; i < len(vals); i++ {
		// 当前值来源于当前值-k
		p.Val = vals[(len(vals)-k+i) %len(vals)]
		p = p.Next
	}
	return head
}

运行结果

Leetcode每日一题-61.旋转链表

原文：https://www.cnblogs.com/blog-zhangtong/p/14584933.html