package code;

import java.util.Stack;

public class Solution {
	
	static class RandomListNode{
		int label;
		RandomListNode next;
		RandomListNode random;
		RandomListNode(int x){
			label=x;
		}
	}
	
	private Stack<Integer> sck=new Stack();
	
 public RandomListNode copyRandomList(RandomListNode head) {
 RandomListNode cloneHead,p,q;
 q=cloneHead=null;
 
 sck.push(1);
 sck.pop();
 
 //
 int i=0;
 for(p=head;p!=null;){
 	RandomListNode rln=new RandomListNode(p.label);
 	rln.next=p.next;
 	q=p;
 	p.next=rln;
 	p=p.next.next;
 }
 //����randomָ��Ķ���
 for(p=head;p!=null;){
 	q=p.next;
 	if(p.random!=null)
 		q.random=p.random.next;
 	
 	p=p.next.next;
 }
 cloneHead=head.next;
 for(p=head.next;p!=null;){
 	if(p.next!=null)
 		p.next=p.next.next;
 	p=p.next;
 }
 return cloneHead;
 }
 
 public static void main(String[] args){
 	RandomListNode head=new RandomListNode(-1);
 	Solution solution=new Solution();
 	solution.copyRandomList(head);
 }
}