面试题35. 复杂链表的复制

冷不防 2023-02-13 05:55 68阅读 0赞

# 题目： #

[面试题35. 复杂链表的复制][35.]  
[138. 复制带随机指针的链表][138.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]

# 题解： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]

## 1. 题解一：HashMap ##

1.  第一遍遍历，复制节点的 val ，next 和 random 暂时为空，并将源节点和克隆节点形成映射存放在一个 HashMap 中。
2.  第二遍遍历，将拷贝的新的节点组织成一个链表。

## 2. 题解二：原地修改（首选） ##

**1. 解释一：**  
哈希的做法，在大多数公司的面试官面前并不是一个满意的答案，所以需要知道**原地修改**的解法才能够从容面对面试。  
**原地修改**解法流程：

1.  复制一个新的节点，放在原有节点之后（将拷贝节点放到原节点后面），如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1’ -> 2 -> 2’ -> 3 - > 3’ -> null；
2.  从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将拷贝节点的随机指针串起来，当然需要判断 cur.random 是否存在；
3.  将复制完的链表一分为二，分离拷贝节点和原节点，变成1->2->3和1’->2’->3’两个链表，后者就是答案。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
注意：  
**node.next 是 node 复制出来的节点 ，node.random.next 也是 node.random 复制出来的节点。**

**2. 解释二：**

1.  输入如下图 \[\[1,2\],\[2,3\],\[3,null\],\[4,null\]\]  
    ![在这里插入图片描述][20200527213732527.png]
2.  复制源节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]
3.  生成克隆节点的 random 指针。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]
4.  将原链表和克隆链表分离。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]  
    **实现的时候，谨记：源节点的 next 就是它的克隆节点。**

# 代码： #

## 1. 代码一：HashMap ##

// 方法1：
    public static Node copyRandomList(Node head) { 
        if(head == null)
        { 
            return null;
        }
        // map中存的是(原节点，拷贝节点)的一个映射
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while(p != null)
        { 
            Node clone = new Node(p.val);
            map.put(p, clone);
            p = p.next;
        }
        p = head;
        // 将拷贝的新的节点组织成一个链表
        while(p != null)
        { 
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }

## 2. 代码二：原地修改（首选） ##

// 方法2：
    public static Node copyRandomList(Node head) { 
        if(head == null)
        { 
            return null;
        }
        // 完成链表节点的复制
        Node cur = head;
        while(cur != null)
        { 
            Node clone = new Node(cur.val);
            clone.next = cur.next;
            cur.next = clone;
            cur = cur.next.next;
        }
        // 完成链表复制节点的随机指针复制
        cur = head;
        while(cur != null)
        { 
            if(cur.random != null) // 注意判断原来的节点有没有random指针
            { 
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 将链表一分为二
        cur = head;
        Node curCopy = head.next;
        Node headCopy = head.next;
        while(cur != null)
        { 
            cur.next = cur.next.next;
            cur = cur.next;
            if(curCopy.next != null)
            { 
                curCopy.next = curCopy.next.next;
                curCopy = curCopy.next;
            }
        }
        return headCopy;
    }

# 参考： #

1.  [图解 链表的深拷贝][Link 1]
2.  [复杂链表的复制-（看了绝对秒懂的思路）简单易懂的三步解决问题][-]
3.  [利用哈希表，秒杀100%java][100_java]
4.  [复制带随机指针的链表][Link 2]
5.  [Java图解从HashMap到常数空间][Java_HashMap]

[35.]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[138.]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527200517859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200527200558927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200527213024314.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202005272130384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200527212857230.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200527213732527.png]: https://img-blog.csdnimg.cn/20200527213732527.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200527213800713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200527213929987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200527214004688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/lian-biao-de-shen-kao-bei-by-z1m/
[-]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/fu-za-lian-biao-de-fu-zhi-jian-dan-yi-dong-de-san-/
[100_java]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/li-yong-ha-xi-biao-miao-sha-100java-by-panc-2/
[Link 2]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/
[Java_HashMap]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/javatu-jie-cong-hashmapdao-chang-shu-kong-jian-by-/