March 27, 2021: give you a head node of the linked list, and rotate the linked list

2021-03-27： Give you a list of the head node head , Rotate the list , Move each node of the list to the right k A place . Input ：head = 1→2→3→4→5, k = 2, Output ：4→5→1→2→3.

Fuda answer 2020-03-27：

1. Find the tail node and calculate the number of linked list nodes .

2. If k Greater than the number of equilinked list nodes , Need modulus ,k It must be [0, Number of nodes ) Within limits . If k=0, Directly back to the head node .

3. Find the reciprocal k+1 The node of .

4. Cache penultimate k node ans.

5. Tail node to head node .

6. Reciprocal k+1 Node Next The pointer is null .

7. return ans.

The code to use golang To write , The code is as follows ：

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
    }
    // Find tail nodes and count 
    cnt := 1
    tail := head
    for tail.Next != nil {
        cnt++
        tail = tail.Next
    }

    k = k % cnt
    if k == 0 { // It's just the head node , You don't have to operate .
        return head
    }

    // Find the penultimate k+1 node 
    fast := head
    slow := head
    k++
    for k > 0 {
        fast = fast.Next
        k--
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    // Cache results 
    ans := slow.Next
    // Tail node to head node 
    tail.Next = head
    // Reciprocal k+1 Node none Next The pointer 
    slow.Next = nil

    return ans
}

// Linked list printing 
func printlnLinkNodeList(head *ListNode) {
    cur := head
    for cur != nil {
        fmt.Print(cur.Val, "\t")
        cur = cur.Next
    }
    fmt.Println()
}

The results are as follows ：

Insert picture description here