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

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 mainimport "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. 旋转链表
评论

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

好知识，才能预见未来

赞赏

0人进行了赞赏支持

好知识，才能预见未来

更多相关文章

随机推荐