链表训练7:复制含有随机指针节点的链表

【题目描述】

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉:★★☆☆

【解答】

方法一:使用额外的存储空间

这道题的难点在于我们需要定位好随机指针,一个比较简单的解法就是把原节点与复制的节点关联起来,可以使用哈希表把他们关联起来。

首先把副节点全部创建出来,然后把原节点与对应的副节点用哈希表关联起来。关联的时候原节点作为key,副节点作为value。例如对于链表 1->2->3->null。创建副节点 1′, 2′, 3’。然后用哈希表关联起来:

key value
1 1′
2 2′
3 3′

之后在把所有副节点连接成一个链表。在连接的时候,我们 可以通过哈希表很容易这找到对应的随机节点。

代码如下

    //方法1:采用哈希表
    public static Node1 copyListWithRand(Node1 head) {
        Map map = new HashMap<>();
        Node1 cur = head;
        while (cur != null) {
            map.put(cur, new Node1(cur.value));
            cur = cur.next;
        }
        //把副节点连接起来
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法2

其实我们也可以不需要哈希表来辅助,也就是说 ,我们是可以做到空间复杂度为 O(1)的,我们可以把复制的副节点插入到原链表中去,这样也能把原节点与副节点进行关联,进而
定位到随机节点。例如,对于链表 1->2->3->null。首先生成副节点 1′, 2′, 3。然后把副节点插入到原节点的相邻位置,即把原链表变成 1->1′->2->2′->3->3′->null。

这样我们也可以在连接副节点的时候,找到相应的随机节点。例如 1 的随机节点是 3,则 1′ 的随机节点是 3’。显然,1节点的随机节点的下一个节点就是 1’的随机节点。具体代码如下:

    //方法二
    public static Node1 copyListWithRand2(Node1 head){
        Node1 cur = head;
        Node1 next = null;

        //把复制的节点插进去
        while (cur != null) {
            next = cur.next;
            Node1 temp = new Node1(cur.value);//复制节点
            temp.next = cur.next;
            cur.next = temp;
            cur = next;
        }
        //在一边把复制的节点取出来一边连接。
        cur = head;
        next = null;
        while (cur != null) {
            next = cur.next.next;//保存原链表的下一个节点
            cur.next.next = next != null ? next.next : null;
            cur.next.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }
        return head.next;
    }

采用这种方法的时候,由于随机节点有可能是空指针,随意写代码的时候要注意。

问题拓展

思考:如果是有两个随机指针呢?又该如何处理呢?三个呢?

如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人,帅地正在疯狂更新中….

发表评论

后才能评论