python-leetcode-随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # Step 1: Create new nodes and insert them after each original node
        cur = head
        while cur:
            new_node = Node(cur.val)
            new_node.next = cur.next
            cur.next = new_node
            cur = new_node.next

        # Step 2: Assign random pointers for the new nodes
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # Step 3: Separate the new list from the original list
        cur = head
        new_head = head.next
        while cur:
            new_node = cur.next
            cur.next = new_node.next
            cur = cur.next
            if new_node.next:
                new_node.next = new_node.next.next

        return new_head