首页 > 试题广场 >

复杂链表的复制

[编程题]复杂链表的复制
  • 热度指数:766212 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针,虚线箭头表示random指针。为简单起见,指向null的指针没有画出。

示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段,前半部分{1,2,3,4,5}为ListNode,后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分,3,5,#,2,#分别的表示为
1的位置指向3,2的位置指向5,3的位置指向null,4的位置指向2,5的位置指向null
如下图:

示例1

输入

{1,2,3,4,5,3,5,#,2,#}

输出

{1,2,3,4,5,3,5,#,2,#}

说明:本题目包含复杂数据结构ListNode、RandomListNode,点此查看相关信息
# -*- coding:utf-8 -*-
旧链表和新链表哈希对应,不是最优方法
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if(pHead == None):
            return None
        nhead = RandomListNode(-1)
        ptr = RandomListNode(-1)
        nhead.next = ptr

        dic = {}
        head = pHead
        while(pHead != None):
            node = RandomListNode(pHead.label)
            ptr.next = node
            ptr = ptr.next
            dic[pHead] = ptr
            if(pHead.next != None):
                pHead = pHead.next
            else:
                break

        while(head.next != None):
            if(head.random != None):
                dic[head].random = dic[head.random]
            head = head.next


        return nhead.next.next

发表于 2021-07-08 19:46:25 回复(0)
from copy import deepcopy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        return deepcopy(pHead)
发表于 2021-07-02 09:54:53 回复(0)
年轻人不讲武德。
import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        return copy.deepcopy(pHead)

发表于 2021-06-01 18:20:59 回复(1)
#根据大佬思路写的python版本
class Solution:
    def Clone(self, pHead):
        #用字典储存旧节点和新节点的对应关系
        map = {None:None}
        cur = pHead
        while cur:
            map[cur] = RandomListNode(cur.label)
            cur = cur.next
        #再把新节点的next和random填上
        cur = pHead
        while cur: 
            map[cur].next = map[cur.next]
            map[cur].random = map[cur.random]
            cur = cur.next
        return map[pHead]

编辑于 2021-03-20 13:55:51 回复(0)
# 字典存储节点映射
    def Clone(self, pHead):
        if pHead is None:
            return
        np = RandomListNode(-1)
        p = np
        h = pHead
        re = {}
        while h is not None:
            q = RandomListNode(h.label)
            re[h] = q
            p.next = q
            p = p.next
            h = h.next
        p = np.next
        h = pHead
        while p is not None and h is not None:
            if h.random is not None:
                p.random = re[h.random]
            p = p.next
            h = h.next
        ret = np.next
        np.next = None
        return ret

发表于 2021-03-13 10:00:15 回复(0)
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        
        # 复制结点
        pNode = pHead
        while pNode:
            pNext = pNode.next
            pCopy = RandomListNode(pNode.label)
            pNode.next = pCopy
            pCopy.next = pNext
            pNode = pNext
            
        # 定位random
        pNode = pHead
        while pNode:
            pRandom = pNode.random
            if pRandom:
                pNode.next.random = pRandom.next
            pNode = pNode.next.next
        
        # 拆分两链表
        pNode = pHead
        pHead2 = pHead.next
        while pNode:
            pNode2 = pNode.next
            pNode.next = pNode2.next
            if pNode2.next:
                pNode2.next = pNode.next.next
            pNode = pNode.next
        return pHead2

发表于 2020-10-14 10:19:54 回复(0)
import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        return copy.deepcopy(pHead)

发表于 2020-09-09 16:08:29 回复(0)

图片说明
详细解释:
1.复制原节点-首先用A的值A.value创建节点A',然后用A'→B,最后A→A',循环复制好所有的节点
2.根据旧链表的random指向,复制新链表的random指向。A.random.next = A.next.random
3.打断链表,拆分出原链表和新的复制链表,用两个指针,一个更新总链表,一个更新复制链表,A→B,A'→B',然后指针均往后移动一个next

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead == None:
            return None
        # 复制node并且添加到之前链表node的后面
        pTmp = pHead
        while pTmp:
            node = RandomListNode(pTmp.label)
            node.next = pTmp.next
            pTmp.next = node
            pTmp = node.next
        pTmp = pHead
        while pTmp:
            if pTmp.random:
                pTmp.next.random = pTmp.random.next
            pTmp = pTmp.next.next
        # 断开原来的node,连接新的node
        # 拆分链表,奇数上的是原列表,偶数上的是复制的新列表
        pTmp = pHead
        newHead = pTmp.next
        pNewTmp = pTmp.next
        while pTmp:
            pTmp.next = pTmp.next.next
            if pNewTmp.next:
                pNewTmp.next = pNewTmp.next.next
                pNewTmp = pNewTmp.next
            pTmp = pTmp.next
        return newHead
递归法:
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead == None:
            return None

        if pHead:
            newHead = RandomListNode(pHead.label)
            newHead.random = pHead.random
            newHead.next = self.Clone(pHead.next)

        return newHead
编辑于 2020-09-01 11:07:32 回复(0)
Python, 用递归很快
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        new_node = RandomListNode(pHead.label)
        new_node.random = pHead.random
        new_node.next = self.Clone(pHead.next)
        return new_node


发表于 2020-08-06 23:25:30 回复(1)
搞不懂为啥要复制再拆分或者用hash,直接构造两个指针,一个遍历原链表,一个构造复制体不就行了?
# -*- coding:utf-8 -*-
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return
        cp = RandomListNode(pHead.label)
        cp.random = RandomListNode(pHead.random.label) if pHead.random else None
        go = pHead.next
        ef = cp
        while go:
            ef.next = RandomListNode(go.label)
            ef.next.random = RandomListNode(go.random.label) if go.random else None
            ef = ef.next
            go = go.next
        return cp

编辑于 2020-06-04 22:43:22 回复(0)

Python Solution

class Solution:
    def Clone(self, head):
        
        cur = head  # 横向复制了链表
        while cur:
            tmp = cur.next
            cur.next = RandomListNode(cur.label)
            cur.next.next=tmp
            cur = tmp
        
        cur = head # 重新定向random
        while cur:
            if cur.random:
                cur.next.random=cur.random.next
            cur = cur.next.next
        
        cur = head # 拆链表
        newHead = RandomListNode(0)
        tmp=newHead
        while cur:
            tmp.next = cur.next
            cur.next=cur.next.next
            cur=cur.next  # 把原来的链表改回去,不然在牛客网的验证里会出错
            tmp=tmp.next
        return newHead.next


最后返回时,要保证原链表恢复成原样,不能还留有复制的那部分,否则会报错:“输出为空,请检查一下你的代码,有没有循环输入处理多个case”

编辑于 2020-06-01 20:10:11 回复(0)
思路如上图:沿着旧链表第一遍遍历时,生成值相同的节点,与此同时,如第二步所示,将这些节点的random指针指向旧链表对应节点的random,再将这些节点的random指向新节点。然后第二遍遍历新数组,将这些节点的random指向其random节点的random节点(也就回到了新链表)。

发表于 2020-03-27 21:35:06 回复(0)

Hash的做法

用dict存储原节点和复制的节点的对应关系,那么有 A的复制的random/next = A的random/next的复制

当然,如果random指向的节点不一定在链表上,直接当有向图做就好,可以参考 马客(Mark) 的做法

# -*- coding:utf-8 -*-
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if pHead == None:
            return None
        # 用dict存储原节点和复制的节点的对应关系,那么有 A的复制的random = A的random的复制
        d = dict()
        p = pHead
        # 注意循环链表的可能
        while p and p not in d:
            copy_node = RandomListNode(p.label)
            d[p] = copy_node
            p = p.next
        p = pHead
        s = set()
        while p and p not in s:
            s.add(p)
            if p.next:
                d[p].next = d[p.next]
            if p.random:
                d[p].random = d[p.random]
            p = p.next
        return d[pHead]
编辑于 2020-03-11 16:43:01 回复(0)
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead is None:
            return None
        clone_assis = {}
        newHead = RandomListNode(pHead.label)
        newHeadpointer = newHead
        nexHead = pHead.next
        radHead = pHead.random
        clone_assis[pHead] = newHead
        while nexHead is not None:
            if nexHead in clone_assis:
                newHeadpointer.next = clone_assis.get(nexHead)
            elif nexHead is not None:
                tmp = RandomListNode(nexHead.label)
                clone_assis[nexHead] = tmp
                newHeadpointer.next = tmp
            else:
                newHeadpointer.next = None
            if radHead in clone_assis:
                newHeadpointer.random = clone_assis.get(radHead)
                #print(radHead.label)
            elif radHead is not None:
                tmp = RandomListNode(radHead.label)
                clone_assis[radHead] = tmp
                newHeadpointer.random = tmp
            else:
                newHeadpointer.random = None
            radHead = nexHead.random
            nexHead = nexHead.next
            newHeadpointer = newHeadpointer.next
        return newHead


发表于 2020-02-06 22:22:47 回复(0)
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None

        # 第一步:在原链表每个节点的后面添加一个复制的节点
        tmp = pHead
        while tmp:
            node = RandomListNode(tmp.label)
            node.next = tmp.next
            tmp.next = node
            tmp = node.next

        # 第二步:为每个复制的节点添加random
        tmp = pHead
        while tmp:
            if tmp.random:
                tmp.next.random = tmp.random.next

            tmp = tmp.next.next

        # 第三步:将含有复制节点的链表分割为两个链表,原始链表和新链表
        tmp = pHead
        res = tmp.next
        while tmp.next:
            p1 = tmp.next
            tmp.next = p1.next
            tmp = p1

        return res

发表于 2020-01-19 17:36:10 回复(0)

python用字典解题

  1. 构造字典 k:原 node, v:与原 node label 相同的 node
  2. 遍历字典,完成对 v 中next 和 random 指向的赋值
    class Solution:
     # 返回 RandomListNode
     def Clone(self, pHead):
         # write code here
        if not pHead:
             return 
         ppHead = pHead
         hashtab = {None:None}
         while pHead:
             node = RandomListNode(pHead.label)
             hashtab.update({pHead: node})
             pHead = pHead.next
         for k in hashtab:
             if k:
                 hashtab[k].next = hashtab[k.next]
                 hashtab[k].random = hashtab[k.random]
         return hashtab[ppHead]
编辑于 2019-12-21 22:01:06 回复(0)
class Solution:
    def Clone(self, head):
        nodeList = []  # 存放各个节点
        randomList = []  # 存放各个节点指向的random节点。没有则为None
        labelList = []  # 存放各个节点的值
        #遍历整个链表
        while head:
            randomList.append(head.random)
            nodeList.append(head)
            labelList.append(head.label)
            head = head.next
        # random节点的索引,如果没有则为-1,返回的是节点的random指针指向的链表的位置
        #node节点对应的random节点的位置
        labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList)
        #此处设定的是空的头节点
        dummy = RandomListNode(0)
        pre = dummy
        # 节点列表,只要把这些节点的random设置好,顺序串起来就ok了。
        #很简单的一个创建新链表的过程
        nodeList = map(lambda c: RandomListNode(c), labelList)
        # 把每个节点的random绑定好,根据对应的index来绑定
        for i in range(len(nodeList)):
            if labelIndexList[i] != -1:
                nodeList[i].random = nodeList[labelIndexList[i]]
        for i in nodeList:
            pre.next = i
            pre = pre.next
        #既改变了dummy所引导的链表,但是又没有改变链表头
        return dummy.next
说实话,本题我并没有做出来,主要原因是我的random赋值是直接赋值,这样是有问题的,应该通过列表索引的方法找到对应节点的random节点的位置,因为这两个链表是不同的。同时在建立链表的时候,可以使用空头指针的方法,最后返回的时候就返回头指针.next就可以了。
本次使用的是哈希表法,即使用空间换取时间,建立链表的副本,并保存一个哈希表,哈希表中的元素为原节点和复制节点的一个对应,我们最后还需要一个源节点的random节点的位置列表。
发表于 2019-12-18 13:56:22 回复(1)

Python wo lai gao xiao de

import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        ret = copy.deepcopy(pHead)
        return ret


发表于 2019-12-09 19:27:55 回复(0)