剑指25-复杂链表的复制

Posted on | In |

题目描述

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

分解成如下三步：

  • 复制主链表节点。将n1——n2——n3——n4——NULL变成n1——m1——n2——m2——n3——m3——n4——m4———NULL。
  • 复制兄弟连接。如果ni有指向nj的兄弟连接，则通过ni.next.random = ni.random.next建立mi到mj的连接。
  • 分离n节点和m节点，得到原链表n1——n2——n3——n4——NULL和复制链表m1——m2——m3——m4——NULL，兄弟链接在两个链表的节点之间无交叉，故与分离操作无关。通过p.next.next, p.next = p.next.next.next, p.next.next来实现，该语句避免使用中间变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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 is None:
            return None
        
        # 复制主链表，不考虑兄弟链接。兄弟链接的构建需要所有节点都已经存在，因此在之后的一步处理。
        p = pHead
        while p is not None:
            node = RandomListNode(p.label)
            node.next = p.next
            p.next = node
            p = node.next
        
        # 复制兄弟链接
        head = pHead.next
        p = pHead
        while p is not None:
            if p.random is not None:
                p.next.random = p.random.next
            p = p.next.next
        
        # 将两个链表切割
        p = pHead
        while p.next.next:
            p.next.next, p.next = p.next.next.next, p.next.next
            p = p.next
        p.next = None
        return head