剑指offer---25.复杂链表的复制

question:

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的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 curp = pHead; while(curp!=null){ RandomListNode node = new RandomListNode(curp.label); node.next = curp.next; curp.next = node; curp = node.next; } curp = pHead; RandomListNode tmp = null; while(curp!=null){ tmp = curp.next; if(curp.random!=null){ tmp.random = curp.random.next; } curp = tmp.next; } curp = pHead; RandomListNode newHead = pHead.next; while(curp.next!=null){ tmp = curp.next; curp.next = tmp.next; curp = tmp; } return newHead; } }