运维开发网

2021-03-27:给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置

运维开发网 https://www.qedev.com 2021-04-07 14:25 出处:51CTO 作者:福大大
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.尾节点连头节

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

执行结果如下:

2021-03-27:给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置


力扣61. 旋转链表

评论

0

精彩评论

暂无评论...
验证码 换一张
取 消