题解 | #复杂链表的复制#

# -*- 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):
        # 整个复制过程可以分为三步，首先跟随复制所有节点，然后复制random节点，最后拆分两个链表
        if pHead is None:
            return None
        
        # 第一步：影子复制
        cur = pHead
        while cur:
            clone = RandomListNode(cur.label)
            clone.next = cur.next
            cur.next = clone
            cur = clone.next  # 跳到下一个原始节点
        
        # 第二步：复制随机节点指向关系
        cur = pHead
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next  # 跳到下一个原始节点
        
        # 第三步：拆分两个链表
        cur = pHead
        clone_head = pHead.next
        clone_cur = clone_head
        
        while cur:
            cur.next = clone_cur.next
            cur = cur.next
            if clone_cur.next:
                clone_cur.next = cur.next
            clone_cur = clone_cur.next
        
        return clone_head

1. 拆分链表逻辑：在拆分链表的过程中，确保每一次 clone_cur = clone_cur.next 之前检查 clone_cur.next 是否为 None。这样可避免在链表末尾访问空指针。
2. 实例化一个类，就等于创建节点 clone = RandomListNode(cur.label)