剑指offer-25、复杂链表的复制
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个复杂链表（每个节点中有节点值，以及两个指针，⼀个指向下⼀个节点，另⼀个特殊指针random 指向⼀个随机节点），请对此链表进⾏深拷⻉，并返回拷⻉后的头结点。（注意，输出结果中请不要返回参数中的节点引⽤，否则判题程序会直接返回空）</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504012353382.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="哈希表映射">哈希表映射</h3>
<p>使用哈希表存储原节点和新节点的映射关系：</p>
<ol>
<li>第一次遍历：创建所有新节点，并建立原节点到新节点的映射</li>
<li>第二次遍历：根据映射关系设置新节点的<code>next</code>和<code>random</code>指针</li>
</ol>
<pre><code class="language-java">public class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 创建哈希表存储原节点到新节点的映射
HashMap<Node, Node> map = new HashMap<>();
Node current = head;
// 第一次遍历：创建所有新节点并建立映射
while (current != null) {
map.put(current, new Node(current.val));
current = current.next;
}
// 第二次遍历：设置新节点的next和random指针
current = head;
while (current != null) {
Node newNode = map.get(current);
newNode.next = map.get(current.next);
newNode.random = map.get(current.random);
current = current.next;
}
return map.get(head);
}
}
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，两次遍历链表</li>
<li><strong>空间复杂度</strong>：O(n)，需要存储所有节点的映射关系</li>
</ul>
<h3 id="节点插入拆分法">节点插入拆分法</h3>
<p>通过在原链表中插入新节点来避免使用额外空间：</p>
<ol>
<li><strong>节点复制插入</strong>：在每个原节点后面插入一个复制的新节点</li>
<li><strong>设置random指针</strong>：新节点的random指向原节点random的下一个节点</li>
<li><strong>链表拆分</strong>：将混合链表拆分为原链表和新链表</li>
</ol>
<pre><code class="language-java">public class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步：在每个节点后面插入复制的节点
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// 第二步：设置复制节点的random指针
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// 第三步：拆分链表
Node newHead = head.next;
current = head;
while (current != null) {
Node temp = current.next;
current.next = temp.next;
if (temp.next != null) {
temp.next = temp.next.next;
}
current = current.next;
}
return newHead;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，三次遍历链表</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定数量的指针变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19054746
頁:
[1]