题目:复杂链表的复制
描述:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针,虚线箭头表示random指针。为简单起见,指向null的指针没有画出。
示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段,前半部分{1,2,3,4,5}为ListNode,后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分,3,5,#,2,#分别的表示为
1的位置指向3,2的位置指向5,3的位置指向null,4的位置指向2,5的位置指向null
如下图:
思路:在原节点后面插入相同的节点,原节点的next指向新节点
遍历复制的节点
拆分链表
Java代码如下所示:
public class Solution{ /** * @param pHead * @return */ public RandomListNode Clone(RandomListNode pHead) { RandomListNode oldNode=pHead; if(pHead==null){ return null; } //复制每个节点并插入到原节点后面 while(oldNode!=null){ RandomListNode newNode=new RandomListNode(oldNode.label); //生成一个新节点,和原节点一样 newNode.next=oldNode.next; //将newNode插入原节点和他的next节点之间 oldNode.next=newNode; oldNode=oldNode.next.next; //指向下一个原节点 } //将新节点的随机节点设好 oldNode=pHead; while(oldNode!=null){ RandomListNode newNode=oldNode.next; //oldnode的next节点就是复制的原节点 if(oldNode.random!=null){ newNode.random=oldNode.random.next; //原节点的复制的新节点的random指向的随机节点 } oldNode=newNode.next; } //将原来的链表进行拆分 oldNode=pHead; RandomListNode copyHead=oldNode.next; while(oldNode!=null){ RandomListNode copyNode=oldNode.next; //指向复制出来的第一个节点 oldNode.next=copyNode.next; //指向原节点的原来的next节点 if(copyNode.next!=null){ copyNode.next=copyNode.next.next; //更新复制节点的next } oldNode=oldNode.next; //更新原节点的next } return copyHead; } }
时间复杂度:需要遍历节点,时间复杂度为0(N)。