Java详解剑指offer面试题35复杂链表的复制

输入一个复杂链表&＃xff08;每个节点中有节点值&＃xff0c;以及两个指针&＃xff0c;一个指向下一个节点&＃xff0c;另一个特殊指针指向任意一个节点&＃xff09;&＃xff0c;返回结果为复制后复杂链表的head。&＃xff08;注意&＃xff0c;输出结果中请不要返回参数中的节点引用&＃xff0c;否则判题程序会直接返回空&＃xff09;


复杂链表的定义如下

private class RandomListNode {int label;RandomListNode next &＃61; null;RandomListNode random &＃61; null;RandomListNode(int label) {this.label &＃61; label;}
}


**注意不可将链表头结点引用返回&＃xff0c;所以需要自己new一个结点出来。**要完成复杂链表的复制&＃xff0c;第一步要完成普通链表的复制&＃xff0c;普通链表的复制可以用一个栈复制每一个结点&＃xff0c;之后逐个弹出并连接起来。对于本题有两种策略&＃xff1a;

第一种是&＃xff0c;在复制普通链表时&＃xff0c;将原链表结点和复制链表的结点成对存入HashMap中&＃xff0c;建立一对一的映射。当进行随机结点复制时&＃xff0c;遍历原链表&＃xff0c;如果某结点的随机结点不为空&＃xff0c;那么根据HashMap能以O(1)的时间找到对应的复制链表结点中&＃xff0c;若原始链表的结点M指向随机结点S&＃xff0c;那么复制链表的M’也要指向结点S’&＃xff0c;这种方法时间复杂度为O(N)&＃xff0c;但空间复杂度为O(N)。

更好的方法是&＃xff0c;插入、连接、拆分三步法。

• 插入&＃xff1a;在原始链表的每个结点后插入一个值和它一样的新结点&＃xff1b;则有oriNode.next &＃61;&＃61; cloneNode这样的关系&＃xff1b;
• 连接随机结点&＃xff1a;遍历插入新结点后的链表&＃xff0c;在访问原始链表中的那些结点时&＃xff0c;判断其是否有随机结点&＃xff0c;有的话cloneNode.random &＃61; oriNode.random.next这里oriNode.random.next表示原始链表随机结点的下一个结点&＃xff0c;其实就是复制链表的随机结点。
• 拆分原始链表和复制链表&＃xff1a;将奇数结点相连就是原始链表&＃xff0c;将偶数结点相连就是我们想要的复制链表。返回复制链表的头结点即可。

package Chap4;/*** 输入一个复杂链表&＃xff08;每个节点中有节点值&＃xff0c;以及两个指针&＃xff0c;一个指向下一个节点&＃xff0c;另一个特殊指针指向任意一个节点&＃xff09;&＃xff0c;返回结果为复制后复杂链表的head* &＃xff08;注意&＃xff0c;输出结果中请不要返回参数中的节点引用&＃xff0c;否则判题程序会直接返回空&＃xff09;*/
public class CloneLinkedList {private class RandomListNode {int label;RandomListNode next &＃61; null;RandomListNode random &＃61; null;RandomListNode(int label) {this.label &＃61; label;}}/*** 1、为每个结点的next插入一个和该结点的值一样的结点* 2、设置每个复制结点的random结点* 3、将链表拆分&＃xff0c;返回复制链表的头结点** &＃64;param pHead 原链表头结点* &＃64;return 复制链表的头结点&＃xff0c;不可直接返回原链接结点的引用&＃xff0c;必须使用new出来的RandomListNode*/public RandomListNode Clone(RandomListNode pHead) {if (pHead &＃61;&＃61; null) return null;copyNode(pHead);setCloneRandomNode(pHead);return splitList(pHead);}// 1. 为每个结点的next插入一个和该结点的值一样的结点private void copyNode(RandomListNode head) {RandomListNode cur &＃61; head;while (cur !&＃61; null) {RandomListNode cloneNode &＃61; new RandomListNode(cur.label);cloneNode.next &＃61; cur.next;cur.next &＃61; cloneNode;cur &＃61; cloneNode.next;}}// 2. 设置每个复制结点的randomprivate void setCloneRandomNode(RandomListNode head) {RandomListNode cur &＃61; head;while (cur !&＃61; null) {RandomListNode cloneNode &＃61; cur.next;if (cur.random !&＃61; null) {cloneNode.random &＃61; cur.random.next;}cur &＃61; cloneNode.next;}}// 3. 拆分链表private RandomListNode splitList(RandomListNode head) {RandomListNode cur &＃61; head;RandomListNode cloneHead &＃61; cur.next;while (cur !&＃61; null) {RandomListNode cloneNode &＃61; cur.next;cur.next &＃61; cur.next.next;if (cloneNode.next !&＃61; null) {cloneNode.next &＃61; cloneNode.next.next;}cur &＃61; cur.next;}return cloneHead;}
}

该方法没有用到额外的空间&＃xff0c;仅仅是对每个结点进行插入、删除操作等。时间复杂度为O(N).

本文参考文献&＃xff1a;
[1]github.com/haiyusun/data-structures