剑指Offer：复杂链表的复制（Python）

清疚 2023-07-17 07:09 5阅读 0赞

## 题目 ##

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

## 思路 ##

将大问题转变为小问题，每次都进行复制头部节点，然后进行递归，每次同样处理头部节点。

## 解答 ##

**方法一**

class RandomListNode:
        def __init__(self, x):
            self.label = x
            self.next = None
            self.random = None
    
    class Solution:
        # 返回RandomListNode
        def Clone(self, pHead):
            # 复制头部节点
            if pHead is None:
                return None
    
            newHead = RandomListNode(pHead.label)
            newHead.next = pHead.next
            newHead.random = pHead.random
    
            # 递归其他节点
            newHead.next = self.Clone(pHead.next)
    
            return newHead.label

## 思路 ##

深拷贝

**方法二**

class RandomListNode:
        def __init__(self, x):
            self.label = x
            self.next = None
            self.random = None
    
    import copy
    class Solution:
        # 返回RandomListNode
        def Clone(self, pHead):
            ret = copy.deepcopy(pHead)
            return ret.label

## 思路 ##

复制每一个节点及节点之间的链接方式，然后断开

**方法三**

class RandomListNode:
        def __init__(self, x):
            self.label = x
            self.next = None
            self.random = None
    
    class Solution:
        # 返回RandomListNode
        def Clone(self, pHead):
            # 1.复制一个一样的node，并且添加到之前的链表的每一个node后面
            if pHead is None:
                return None
            p = pHead
            while p:
                node = RandomListNode(p.label)
                node.next = p.next
                p.next = node
                p = node.next
    
            # 实现node的random的指向
            p = pHead
            while p:
                if p.random:
                    p.next.random = p.random.next
                p = p.next.next
    
            # 断开原来的node和新的node之间的链接
            head = pHead
            res = pHead.next
            while head.next:
            	tmp = head.next
            	head.next = tmp.next
            	head = tmp
            return res