Leetcode 138. 复制带随机指针的链表

发表于
| 字数统计: 288 | 阅读时长 ≈ 1

题目描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 

1
2
3
4
5
6
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

分析

代码

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        node = head
        while node:
            next_node = node.next
            node.next = Node(node.val, next_node, node.random)
            node = node.next.next
        node = head.next
        while node.next:
            node.random = node.random.next if node.random else None
            node = node.next.next
        node.random = node.random.next if node.random else None
        old_node = head
        new_node = head.next
        cloned = head.next
        while new_node.next:
            old_node.next = old_node.next.next
            new_node.next = new_node.next.next
            old_node = old_node.next
            new_node = new_node.next
        old_node.next = None
        return cloned