LeetCode138. 复制带随机指针的链表

题目链接：LeetCode138

题解

第一步：复制结点，复制的结点放在待复制的结点后，依然组成一个单链表
第二步：串接随机指针
第三步：将原单链表与复制链表拆开

代码

class Solution {

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        copyNode(head);
        linkRandomPointer(head);

        return splitList(head);
    }

    /**
     * 复制结点，复制的结点放在待复制的结点后，依然组成一个单链表
     *
     * @param head 链表头
     */
    public void copyNode(RandomListNode head) {
        // 记录当前要被复制的缜
        RandomListNode node = head;
        while (node != null) {
            // 复制一个新的结点
            RandomListNode copyNode = new RandomListNode(node.label);
            // 将结点串接到被复制的结点后，并且依然组成单链表
            copyNode.next = node.next;
            node.next = copyNode;
            node = copyNode.next;
        }
    }

    /**
     * 串接随机指针
     *
     * @param head 链表头
     */
    public void linkRandomPointer(RandomListNode head) {
        // 记录当前要被复制的缜
        RandomListNode node = head;
        while (node != null) {
            // 随机指针有指向某个具体的结点
            if (node.random != null) {
                // 串接node被复制结点的随机指针
                node.next.random = node.random.next;
            }

            // 指向下一个被复制的结点
            node = node.next.next;
        }
    }

    /**
     * 将链表拆分，还原原来的链表，并且组装拷贝的链表
     *
     * @param head 链表头
     * @return 拷贝的新链表头
     */
    public RandomListNode splitList(RandomListNode head) {
        // 新链表头
        RandomListNode copyHead = head.next;
        // 当前处理的被复制的结点
        RandomListNode node = head;
        // 当前复制的结点
        RandomListNode copy;

        while (node != null){
            // 指向复制结点
            copy = node.next;

            // node.next指向下一个被复制的结点
            node.next = copy.next;

            // 下一个被复制的结点不为null
            if (node.next != null) {
                // copy.next指向下一个复制的结点
                copy.next = node.next.next;
            }

            // node指向下一个要被处理的被复制结点
            node = node.next;
        }
        return copyHead;
    }
}

另一种做法

利用哈希表，HashMap的key是Node类型，value也是Node类型，首先遍历一遍链表，将经过的所有结点都拷贝一份相同值的新结点，这一对结点存到哈希表中

然后再重新遍历结点，此时遍历结点的目的就是为了构建next指针和random指针。具体做法就是，将拷贝的结点的next指针设为key的next指针指向的结点，也就是map.get(cur).next=map.get(cur.next)。同样的，将拷贝节点的random指针设为key的random指针指向的结点，也就是map.get(cur).random=map.get(cur.random)

代码

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * }
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = head;
        while(cur != null) {
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}