2021-03-27：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。输入：head = 1→2→3→4→5, k = 2，输出：4→5→1→2→3。
福大大 答案2020-03-27：
1.找尾节点并且计算链表节点个数。
2.如果k大于等链表节点个数，需要取模，k一定在[0,节点个数)范围之内。如果k=0，直接返回头节点。
3.求倒数k+1的节点。
4.缓存倒数第k节点ans。
5.尾节点连头节点。
6.倒数k+1节点的Next指针为空。
7.返回ans。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
printlnLinkNodeList(head)
k := 6
fmt.Println("k =", k)
fmt.Println("----------------")
ret := rotateRight(head, k)
printlnLinkNodeList(ret)
}
type ListNode struct {
Val int
Next *ListNode
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
//找尾节点并且计数
cnt := 1
tail := head
for tail.Next != nil {
cnt++
tail = tail.Next
}
k = k % cnt
if k == 0 { //刚好是头节点，就不用操作了。
return head
}
//找倒数第k+1节点
fast := head
slow := head
k++
for k > 0 {
fast = fast.Next
k--
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
//缓存结果
ans := slow.Next
//尾节点连头节点
tail.Next = head
//倒数k+1节点无Next指针
slow.Next = nil
return ans
}
//链表打印
func printlnLinkNodeList(head *ListNode) {
cur := head
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next
}
fmt.Println()
}
执行结果如下：
在这里插入图片描述
