2021-04-09:rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。给定一

举报
福大大架构师每日一题 发表于 2021/04/09 21:53:09 2021/04/09
【摘要】 2021-04-09:rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。 【要求】时间复杂度O(N),额外空间复杂度O(1) 。福大大 答案2021-04-09:假设链表节点是A1→B1→C1。1.复制节点,插入原链表,...

2021-04-09:rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。 【要求】时间复杂度O(N),额外空间复杂度O(1) 。

福大大 答案2021-04-09:

假设链表节点是A1→B1→C1。
1.复制节点,插入原链表,链表变成A1→A2→B1→B2→C1→C2。
2.设置A2、B2、C2的随机指针。
3.拆分链表。变成A1→B1→C1和A2→B2→C2。
4.返回A2→B2→C2。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    head := &Node{Val: 1}
    head.Next = &Node{Val: 2}
    head.Next.Next = &Node{Val: 3}
    head.Next.Next.Random = head
    fmt.Print("原结构:")
    printlnLinkNodeList(head)
    ret := copyRandomList(head)
    fmt.Print("复制结构:")
    printlnLinkNodeList(ret)
}

// Definition for a Node.
type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    //复制节点
    cur := head
    var curCopy *Node
    for cur != nil {
        curCopy = &Node{Val: cur.Val}
        curCopy.Next = cur.Next
        cur.Next = curCopy
        cur = curCopy.Next
    }
    //设置随机节点
    cur = head
    for cur != nil && cur.Next != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }

    //分离成两个链表
    cur = head
    headCopy := head.Next
    for cur != nil && cur.Next != nil {
        next := cur.Next
        cur.Next = cur.Next.Next
        cur = next
    }

    //返回复制链表
    return headCopy
}

//链表打印
func printlnLinkNodeList(head *Node) {
    cur := head
    for cur != nil {
        if cur.Random != nil {
            fmt.Print(cur.Val, "_", cur.Random.Val, " ")
        } else {
            fmt.Print(cur.Val, "_nil ")
        }
        cur = cur.Next
    }
    fmt.Println()
}

执行结果如下:
在这里插入图片描述


左神java代码
力扣138. 复制带随机指针的链表
评论

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。