2021-03-27：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。输入：head = 1→2→3→4→5, k = 2，输出：4→5→1→2→3。

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()

}

执行结果如下：

---

力扣61. 旋转链表

评论

2021-03-27：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。输入：head = 1→2→3→4→5, k = 2，输出：4→5→1→2→3。的相关教程结束。