Copy List with Random Pointer

Copy List with Random Pointer

---

三天没有推送了，很是抱歉。因为这几天都在公司加班，年底有项目要上线，催得紧。而且，每天晚上在中关村附近打车都很艰难，回到家都已经很晚了。在公众平台有朋友给我留言说“博主加油”，真的很感动，感谢各位的关注。以后我会尽量遵守我的诺言，争取每天都更新。

言归正传，今天是一道有关链表题目，来自LeetCode，难度为Medium，Acceptance为27%。

题目如下

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

因为该题已经在《剑指offer》等书上收录了，相信各位也都看过这道题。所以，我不打算做过多的解释，但是会给出详细的步骤和代码。

首先，该题的难点在于因为每个节点都有一个随机指针，不能直接遍历一遍链表就能复制出来；第一次遍历复制所有的节点，然后需要再遍历一次来链接随机指针。

然后，有了上述思路之后，就可以将问题转化为如何记录随机指针指向的节点。

思路一：用一个map，以原节点为键，以复制出来的节点为值。这样就可以在第二次遍历时，就可以O(1)的时间复杂度找到这个随机指针指向的节点。

思路二：该方法也是在各大书籍上采用的方法。主要包含三步：第一步，遍历链表，在每个节点后面插入该节点的复制节点，如A->B->C插入新节点后A->A1->B->B1->C->C1；第二步，再次遍历链表，链接随机指针，如原链表中有A->C的随机指针，在遍历时只需让A.next.random->A.random.next即可得到A1->C1；第三步：分拆链表，即由A->A1->B->B1->C->C1分拆为A->B->C和A1->B1->C1。

下面给出思路二的代码。

代码如下

java版

/**
 * 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 {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        if(null == head)
            return null;
        RandomListNode p = head;
        while(p != null){
            RandomListNode node = new RandomListNode(p.label);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        p = head;
        while(p != null){
            if(p.random != null)
                p.next.random = p.random.next;
            p = p.next.next;
        }
        p = head;
        RandomListNode newhead = new RandomListNode(0), cur = newhead;
        while(p != null){
            RandomListNode node = p.next;
            p.next = node.next;
            p = p.next;
            cur.next = node;
            cur = node;
        }
        return newhead.next;
    }
}