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

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/copy-list-with-random-pointer/
Star
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
notion imagenotion image
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
  • 0 <= n <= 1000
  • 10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。

法1 hash表格

思路
采用hash表先保存节点，保存格式如下。字典：老节点（key） 新节点（value）
然后根据原先的节点将新节点建立对应的关系
题解
"""
# 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: 'Node') -> 'Node':
        if head is None:
            return head
        hashTable = {}
        cur = head
        while cur:
            hashTable[cur] = Node(cur.val)
            cur = cur.next
        
        cur = head
        while cur:
            # cur 是原节点
            # hashTable[cur] 是复制的节点
            hashTable[cur].next = hashTable[cur.next] if cur.next else None
            hashTable[cur].random = hashTable[cur.random] if cur.random else None
            cur = cur.next
        return hashTable[head]

法2 复制节点跟在源节点之后

思路
采用hash表格的核心思路是：新复制的节点和原先的节点对应关系 保存了下来。那么我可以不用hash表，而是直接将新复制的节点放到原始的节点之后，这样源节点和新复制的节点的对应关系也一一对应了起来。
第一次遍历 将新复制的节点跟在对应的节点后面. 第二次遍历修改rand指针 第三次遍历提取偶数个节点
题解
"""
# 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: 'Node') -> 'Node':
        if head is None:
            return head
        
        # 复制节点到原节点后面
        cur = head
        while cur:
            next_ = cur.next
            newNode = Node(cur.val)
            cur.next = newNode
            newNode.next = next_
            cur = next_
        
        # 连接复制节点的random
        cur = head
        while cur:
            next_ = cur.next.next
            cur.next.random = cur.random.next if cur.random else None
            cur = next_
        
        # 从中抽取偶数节点
        res = head.next
        cur = head
        while cur:
            next_ = cur.next.next
            curCopy = cur.next
            curCopy.next = next_.next if next_ else None
            cur.next = next_
            cur = next_
        return res
# --------------或者这么写更清晰
				# 奇偶节点剥离开来
        old = head
        cur = head.next
        dummy = Node(-1, cur)
        while old:
            old.next = cur.next
            cur.next = cur.next.next if cur.next else None
            
            old = old.next
            cur = cur.next

        return dummy.next