LeetCode 剑指 Offer 35. 复杂链表的复制

Categories:

题目描述
思路分析
1. 解法一：哈希表（推荐）
相似题目

题目描述

✅ 剑指 Offer 35. 复杂链表的复制

思路分析

解法一：哈希表（推荐）

核心思路：

第一遍遍历创建新节点，并用哈希表记录 旧节点 -> 新节点。

第二遍遍历补全 next 与 random 指针。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(n)，哈希表保存映射关系。

// 哈希表映射旧节点到新节点
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            Node node = map.get(cur);
            node.next = map.get(cur.next);
            node.random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

// 哈希表映射旧节点到新节点
func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}

	m := make(map[*Node]*Node)
	cur := head
	for cur != nil {
		m[cur] = &Node{Val: cur.Val}
		cur = cur.Next
	}

	cur = head
	for cur != nil {
		node := m[cur]
		node.Next = m[cur.Next]
		node.Random = m[cur.Random]
		cur = cur.Next
	}

	return m[head]
}

相似题目

题目	难度	考察点
138. 随机链表的复制	中等	哈希表
133. 克隆图	中等	哈希表
148. 排序链表	中等	链表
146. LRU 缓存	中等	哈希表
430. 扁平化多级双向链表	中等	链表
1171. 从链表中删去总和值为零的连续节点	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/52496978