*面试题35：复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

知识点

链表

---

Qiang的思路

这道题提出了一种复杂链表，然后定义它的复制操作。如果是一个普通的链表，值需要对每个节点复制，然后遵循之前的指向连接起来就可以了，但是对于这个复杂链表，仅仅这样做是肯定无法实现对其复制的。但是思路是一样的。

针对next指针，我们可以按照普通链表复制的方式，一个节点一个节点的复制，并将指向也复制过来。这样就可以得到一个没有random指向的复杂链表。

接下来就是要将random指针的指向还原。想要还原这个指针，我们必须要知道一个指针指向的节点对应在链表中的位置，然后根据这个问题去找到新链表中的节点，然后然后random指针的复制。

对于这个位置问题，我们可以理解为找到一个节点和其在链表中位置的对应关系，所以也就想到了用字典去实现这个功能。

于是定义了一个字典，键就是节点，值就是节点在链表中的位置。然后便可以知道random指向的节点在链表中的位置了。为了不用每次遍历链表寻找该位置的节点，我们使用了一个list存储所有的节点，并保持去位置顺序不变。这样就可以根据位置在常数级的时间内找到节点，然后完成random指针的复制操作。

# -*- 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
        l=[]
        d={}
        result=RandomListNode(pHead.label)
        l.append(result)
        pre=result
        root=pHead.next
        d[pHead]=0
        count=1
        while root!=None:
            pre.next=RandomListNode(root.label)
            pre=pre.next
            d[root]=count
            root=root.next
            count+=1
            l.append(pre)
        count=0
        while pHead!=None:
            if pHead.random!=None:
                l[count].random=l[d[pHead.random]]
            pHead=pHead.next
            count+=1
        return result

这道题也是一直卡着没过，一开始的时候倒数第4,5行没有判断，也就是没有倒数第5行，但是这就会有一个问题，因为链表中的next指针除了尾节点其余的节点都是有的，但是random指针每个节点都有可能没有，所以直接使用这个指针作为键去索引对应的值是有问题的。最后通过一个判断解决了该问题。

---

Book中的思路

书中给出了一种思路，可以在不适用辅助空间的基础上完成该功能。

具体是在进行节点复制时将每一个节点复制的节点放到该节点的后面，当完成一遍节点复制之后相当于将原来的链表变为原来的一倍，每个节点在相邻的位置重复出现。这样在进行random指针的复制时只需要按照原节点的random指向，将当前节点的random指向原节点random指针的下一个节点即可。

但是在编程时还是遇到了问题，下面是错误的程序。

# -*- 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
        root=pHead
        while root!=None:
            node=RandomListNode(root.label)
            node.next=root.next
            root.next=node
            root=root.next.next
        result=RandomListNode(None)
        pre=result
        root=pHead
        while root!=None:
            pre.next=root.next
            pre=pre.next
            if root.random!=None:
                pre.random=root.random.next
            root=root.next.next
        return result.next

错误描述：空。请检查一下你的代码，有没有循环输入处理多个case。点击查看如何处理多个case

目前还目前解决，先放一下，回头再看看。

---

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。