描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意：新链表不能指向原链表节点）。

下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

思路1：使用Map

1. 使用Map存储旧链表节点和新链表节点的映射Map<RandomListNode, RandomListNode>
2. 再次遍历，给新链表节点的next和random赋值

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p1 = pHead;
        while(p1 != null) {
            map.put(p1, new RandomListNode(p1.label));
            p1 = p1.next;
        }
        p1 = pHead;
        while(p1 != null) {
            RandomListNode node = map.get(p1);
            node.next = map.get(p1.next);
            node.random = map.get(p1.random);
            p1 = p1.next;
        }
        return map.get(pHead);
    }
}

思路2：复制节点，再拆分

1. 遍历在原链表上复制节点
2. 再次遍历给random赋值
3. 再拆分两个链表

1->2->3复制之后变为1->1'->2->2'->3->3'

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }
        RandomListNode p1 = pHead;
        //修改原链表，复制每一个节点
        while(p1 != null) {
            RandomListNode node = new RandomListNode(p1.label);
            node.next = p1.next;
            p1.next = node;
            p1 = node.next;
        }
        p1 = pHead;
        //给新节点的random赋值
        while(p1 != null) {
            if(p1.random != null) {
                p1.next.random = p1.random.next;   
            }
            p1 = p1.next.next;
        }
        p1 = pHead;
        RandomListNode ret = pHead.next;
        RandomListNode p2 = p1.next;
        //拆分链表
        while(p2.next != null) {
            p1.next = p1.next.next;
            p2.next = p2.next.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        //将旧链表与新链表断开
        p1.next = null;
        return ret;
    }
}

思路3：暴力破解

1. 先遍历创建新链表，random指向原链表节点
2. 同时遍历新链表和旧链表，找到对应的random节点
3. 给新链表的每个节点random赋值

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode p1 = pHead;
        RandomListNode ret = new RandomListNode(pHead.label);
        RandomListNode p2 = ret;
        p2.random = p1.random;
        //创建新链表，random指向原链表
        while(p1.next != null) {
            p1 = p1.next;
            p2.next = new RandomListNode(p1.label);
            p2 = p2.next;
            p2.random = p1.random;
        }
        p2 = ret;
        //遍历新链表
        while(p2 != null) {
            p1 = pHead;
            RandomListNode tmp = ret;
            //同时遍历两个链表，找到原链表中的random节点，此时也找到了新链表中对应的节点
            while(p2.random != p1) {
                p1 = p1.next;
                tmp = tmp.next;
            }
            p2.random = tmp;
            p2 = p2.next;
        }
        return ret;
    }
}