【面试题24】复杂链表的复制

时间:2022-09-14 23:26:22

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

/*
public class RandomListNode {
     int label;
     RandomListNode next = null;
     RandomListNode random = null;
 
     RandomListNode(int label) {
         this.label = label;
     }
}
*/
public class Solution {
     
     private void copyNext(RandomListNode head){
         if (head== null ){
             return ;
         }
         while (head!= null ){
             RandomListNode newNode= new RandomListNode(head.label);
             newNode.random=head.random;
             newNode.next=head.next;
             head.next=newNode;
             head=head.next.next;
         }
     }
     
     private void copyRandom(RandomListNode head){
         if (head== null ){
             return ;
         }
         while (head!= null ){
             if (head.next.random!= null ){
                 head.next.random=head.random.next;
             }           
             head=head.next.next;
         }
     }
     
     private RandomListNode splitList(RandomListNode head){
         if (head== null ){
             return null ;
         }
         RandomListNode newHead=head.next;
         while (head!= null ){
             RandomListNode temp=head.next;
             head.next=temp.next;
             head=head.next;
             if (temp.next!= null ){
                 temp.next=temp.next.next;
             }
         }
         return newHead;
     }
     public RandomListNode Clone(RandomListNode phead)
     {
      if (phead== null ){
          return null ;
      }  
         copyNext(phead);
         copyRandom(phead);
         return splitList(phead);
     }
}