深拷贝复杂链表 - 哈希

package JianZhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
 */
public class test35 {
    static class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static void main(String[] args) {
        Node n=new Node(7);
        n.next=new Node(13);
        n.random=null;
        n.next.next=new Node(11);
        n.next.random=new Node(0);
        n.next.next.next=new Node(10);
        n.next.next.random=new Node(4);
        n.next.next.next.next=new Node(1);
        n.next.next.next.random=new Node(0);
        Node result=copyRandomList(n);    
    }
    public static Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Map<Node,Node> map=new HashMap<>();
        Node curr=head;
        while(curr!=null){
            map.put(curr, new Node(curr.val));
            curr=curr.next;
        }
        curr=head;
        while(curr!=null){
            map.get(curr).next=map.get(curr.next);
            map.get(curr).random=map.get(curr.random);
            curr=curr.next;
        }

        return map.get(head);
        
        // Node temp=new Node(head.val);
        
        // Node temph=temp;
        // while(head!=null){
        //     if(head.next==null){
        //         temp.next=null;
        //     }else{
        //         temp.next=new Node(head.next.val);
        //     }
        //     if(head.random==null){
        //         temp.random=null;
        //     }else{
        //         temp.random=new Node(head.random.val);
        //     }
            
        //     head=head.next;
        //     temp=temp.next;
        // }
        // return temph;
    }
    
}

 

上一篇:全排列算法及解决数字搭积木问题


下一篇:LeetCode基础_树_祖先系列