链表的深拷贝

拼搏现实的明天。 2022-05-23 08:55 99阅读 0赞

![这里写图片描述][70]

class RandomListNode {
          int label;
          RandomListNode next, random;
          RandomListNode(int x) { this.label = x; }
    }
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null||head.next==null)
               return head;
            RandomListNode newHead=new RandomListNode(head.label);
            RandomListNode tmp=newHead;
            RandomListNode tmp2=head;
            while(tmp2.next!=null){
                tmp2=tmp2.next; 
                tmp.next=new RandomListNode(tmp2.label);
                tmp=tmp.next;
            }
            //重新指向链表的头部
            tmp=newHead;
            tmp2=head; 
            while(tmp2!=null&&tmp!=null){
                RandomListNode rand=tmp2.random; //随机指针
                RandomListNode cur=newHead;
                while(rand!=null&&cur!=null){
                   if(cur.label==rand.label){
                      tmp.random=cur;
                      break;
                   }else{
                       cur=cur.next;
                   }
                }
                tmp2=tmp2.next;
                tmp=tmp.next;  
            }
            return newHead;
        } 
       //打印链表的值
        public void printList(RandomListNode head){
            while(head!=null){
               System.out.print(head.label+" ");
               if(head.random!=null)
               System.out.print("随机值:("+head.random.label+") ");
               head=head.next;
            }
            System.out.println();
        }
        public static void main(String[]args){
            //System.out.println("Hello ");
            RandomListNode head=new RandomListNode(-1);
            RandomListNode second=new RandomListNode(8);
            RandomListNode third=new RandomListNode(7);
            RandomListNode four=new RandomListNode(-3);
            RandomListNode five=new RandomListNode(4);
            head.next=second;
            second.next=third;
            third.next=four;
            four.next=five;
            //4,-3,#,#,-1 
            head.random=five;
            second.random=four;
            five.random=head;
            Solution s=new Solution();
            s.printList(head);
            s.printList(s.copyRandomList(head));
        }
    }

[70]: /images/20220523/14e77506fa5d467789c604383cf61df3.png