题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
思路
第一步,在每个节点的后面插入复制的节点。
第二步,对复制节点的 random 链接进行赋值。
第三步,拆分。
实现
/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) return null; RandomListNode tmpHead = pHead; // 先克隆所有的节点并插入到该节点之后 while(tmpHead != null){ RandomListNode insert = new RandomListNode(tmpHead.label); insert.next = tmpHead.next; tmpHead.next = insert; tmpHead = insert.next; } tmpHead = pHead; // 克隆所有节点的random节点 while(tmpHead != null){ if(tmpHead.random != null){ tmpHead.next.random = tmpHead.random.next; } tmpHead = tmpHead.next.next; } tmpHead = pHead; RandomListNode clone = pHead.next; //RandomListNode tmpClone = clone; // 重新调整所有节点的next节点 while(tmpHead.next != null){ RandomListNode tmp = tmpHead.next; tmpHead.next = tmp.next; tmpHead = tmp; } return clone; } }
思路参考:https://www.nowcoder.com/discuss/198840