Leetcode 随机链表的复制

算法思想（O(n) 时间复杂度，O(1) 空间复杂度）

这道题的目的是复制一个带有随机指针的链表。由于链表中的 random 指针可能指向任意节点或者 null，我们需要确保新链表中的 random 指针正确地指向对应的新节点。
为了在不使用额外空间（如 HashMap）的情况下完成复制，我们采用三步法，通过在原链表中插入新节点并逐步分离来完成复制。

---

🚀 算法步骤

步骤 1️⃣：克隆节点并插入原链表

我们首先创建新节点，并插入到原节点的后面，使得新节点和原节点交错排列，例如：

原链表：
A → B → C → D插入新节点后：
A → A' → B → B' → C → C' → D → D'

📌 实现方式：

• 遍历原链表的每个节点 curr。
• 创建一个 newNode，值与 curr 相同。
• 将 newNode 插入 curr 后面 (curr.next = newNode)。
• 继续向后移动 curr，处理下一个节点。

代码实现：

Node curr = head;
while (curr != null) {Node newNode = new Node(curr.val);newNode.next = curr.next;curr.next = newNode;curr = newNode.next;
}

---

步骤 2️⃣：设置新节点的 random 指针

因为 random 指针可能指向任意位置，我们利用新旧交错的结构来找到正确的 random 目标：

• 如果 curr.random != null，那么 curr.next.random = curr.random.next，即新节点的 random 指向旧节点 random 的下一个节点（即对应的克隆节点）。

示意图：

原来的 random:
A.random → C
B.random → D调整后的 random:
A'.random → C'
B'.random → D'

📌 实现方式：

• 遍历链表，检查每个 curr 节点的 random 指针。
• 将 curr.next.random 设为 curr.random.next（即 random 指向的克隆节点）。

代码实现：

curr = head;
while (curr != null) {if (curr.random != null) {curr.next.random = curr.random.next;}curr = curr.next.next;
}

---

步骤 3️⃣：拆分链表

在这一步，我们将新旧链表分离：

• curr.next 指向 curr.next.next，恢复原链表。
• copy.next 指向 copy.next.next，分离出新链表。

📌 示意图：

合并状态：
A → A' → B → B' → C → C' → D → D'分离后：
原链表：A → B → C → D
复制链表：A' → B' → C' → D'

📌 实现方式：

• curr 遍历原链表，每次将 curr.next 复原为 curr.next.next。
• copy 遍历新链表，每次将 copy.next 指向 copy.next.next。

代码实现：

curr = head;
Node newHead = head.next;
Node copy = newHead;
while (curr != null) {curr.next = curr.next.next;if (copy.next != null) {copy.next = copy.next.next;}curr = curr.next;copy = copy.next;
}

---

⏳ 时间 & 空间复杂度分析

✅ 时间复杂度：O(n)

我们对链表进行了三次遍历：

1. 第一次遍历 创建克隆节点并插入到原链表后面。（O(n)）
2. 第二次遍历 复制 random 指针。（O(n)）
3. 第三次遍历 拆分链表。（O(n)）

综合下来，时间复杂度是 O(n)。

✅ 空间复杂度：O(1)

整个过程中，我们没有额外使用 HashMap 或数组，而是直接修改链表结构，所以空间复杂度为 O(1)。

---

📌 总结

• 使用原地修改的方法（O(1) 额外空间），避免使用 HashMap 存储旧节点到新节点的映射。
• 通过三步法：
  1. 交错插入新节点。
  2. 复制 random 指针。
  3. 拆分链表。
• 时间复杂度 O(n)，空间复杂度 O(1)，比 HashMap 方法更优。

这样，我们就高效地复制了链表，并且保证 random 指针的正确性！🚀

java solution

class Solution {public Node copyRandomList(Node head) {if(head == null) return null; //首先处理特殊情况//step 1. 复制原链表节点,紧跟每个节点后面Node curr = head;while(curr != null) {Node newNode = new Node(curr.val);newNode.next = curr.next;curr.next = newNode;curr = curr.next.next;}//step 2. 复制random指针curr = head;while(curr != null) {if(curr.random != null) {curr.next.random = curr.random.next;}curr = curr.next.next;}//step 3. 分离链表curr = head;Node newHead = head.next;Node copy = newHead;while(curr != null) {curr.next = curr.next.next;if(copy.next != null) {copy.next = copy.next.next;}curr = curr.next;copy = copy.next;}return newHead;}
}