[剑指offer][Java]复杂链表的复制

题目

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

程序核心思想

• 这个题目用的数据结构为hashmap。把原始数据的节点看做键，把复制的节点看做值，这样就是一个键值对，然后存入hashmap中，这一步只进行值的复制。
  然后遍历原始链表，遍历一个节点，就可以拿到这个节点对应的下个节点和随机节点，然后把这两个节点和遍历的当前节点看做是键，就可以从hashmap中取出它们对应的复制节点，然后让遍历的节点的复制的next和random指针，分别指向它们的复制节点即可。
• 第二个解法是不需要使用hashmap的方法。从第一个方法可以看出，hashmap的作用是记录一个节点的复制节点在哪里，所以这一个解法就用了结构来解决这个问题。它把每个节点的拷贝节点放到了源节点的后面，也就是源节点的next指针指向了拷贝节点，然后就处理random指针，源节点的random的指针指向的节点的下一个节点，就是它的拷贝节点的random指针应该指向的节点。最后就是处理原链表和拷贝链表的分开问题，非常简单，不多说了。

在LeetCode中，第一种方法和第二种方法使用的内存是差不多的，但是第二种方法比第一种方法快了一倍。

Tips

HashMap的使用：
添加元素——put()
通过键获取值 —— get()
是否为空 ——isEmpty()
是否包含某个键 —— containsKey()
是否包含某个值 ——containsValue
删除key下的value ——remove(key)
删除一个键值对 ——remove(key, value)
键值对的个数 ——size()

代码

import java.util.HashMap;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null)    return null;
        HashMap<RandomListNode, RandomListNode> hm = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode start = pHead;
        
        while(start != null){
            hm.put(start, new RandomListNode(start.label));
            start = start.next;
        }
        
        start = pHead;
        while(start != null){
            hm.get(start).next = hm.get(start.next);
            hm.get(start).random = hm.get(start.random);
            start = start.next;
        }
        
        return hm.get(pHead);
    }
}

//LeetCode
/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)    return null;
        Node a = head;
        Node b = null;
        Node c = null;
        if(a.next != null){
            b = a.next;
        }else{
            if(a.random == a){
                Node node = new Node(a.val, null, null);
                node.random = node;
                return node;
            }else{
                return new Node(a.val, null, null);
            }
        }
        
        while(b != null){
            a.next = new Node(a.val, b, null);
            a = b;
            b = b.next;
        }
        a.next = new Node(a.val, b, null);
        
        a = head;
        while(a != null && a.next != null && a.next.next != null){
            if(a.random != null){
                a.next.random = a.random.next;
            }else{
                a.next.random = null;
            }
            a = a.next.next;
        }
        if(a.random != null){
                a.next.random = a.random.next;
        }else{
                a.next.random = null;
        }

        a = head;
        b = a.next;
        c = b;
    
        while(b.next != null){
            a.next = b.next;
            a = a.next;
            b.next = a.next;
            b = b.next;
        }

        a.next = null;
        b.next = null;
        return c;
    }
}