复杂链表的复制

问题描述

输入一个复杂链表（每个节点中有结点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）

思路分析

很自然的第一个想法就是采取分治法，首先复制原来链表的结点，把每个复制的结点都链在原结点后面，接下来，设置复制节点的特殊指针，并且如果原来节点指向特殊指针N，则原结点复制后的结点指向N的复制指针，最后，需要抽取出复制的结点，由于原结点与复制节点都是间隔的，所以可间接处理

码上有戏

public class CopyCompLicateLinkedList {

	static class RandomListNode{
		int label;
		 RandomListNode next=null;
		  RandomListNode random=null;
		   
		  RandomListNode(int label){
			  this.label=label;
		  }
	}
	
	//复制链表结点
	private void CloneNodes(RandomListNode pHead){
		RandomListNode node=pHead;
		 while(pHead!=null)
		 {
			 RandomListNode cloneNode=new RandomListNode(node.label);
			   cloneNode.next=node.next;
			    cloneNode.random=null;
			     cloneNode.random=null;
			       node.next=cloneNode;
			         node=cloneNode.next;
		 }
	}
		//设置每个节点的随机指针
		private void ConnectSibLingNodes(RandomListNode pHead){
			 RandomListNode node=pHead;
			  while(node!=null)
			  {
				  RandomListNode clone=node.next;
				   if(node.random!=null)
				   {
					   clone.random=node.random.next;
				   }
				   node=clone.next;
			  }
		}
		
	 //组合复制的结点
	private RandomListNode ConnectFinalListNodes(RandomListNode pHead){
		RandomListNode node=null;
		RandomListNode cloneHead=null;
		RandomListNode cloneNode=null;
		
		if(node!=null){
			cloneHead=node.next;
			 cloneNode=node.next;
			  node.next=cloneNode.next;
			 node=node.next;
		}
		
		while(node!=null){
			cloneNode.next=node.next;
			 cloneNode=cloneNode.next;
			  node.next=cloneNode.next;
			  node=node.next;
		}
		return cloneHead;
	}
	
	public RandomListNode Clone(RandomListNode pHead){
		this.CloneNodes(pHead);
		 this.ConnectSibLingNodes(pHead);
		  return this.ConnectFinalListNodes(pHead);
	}