欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-06 11:03:53
...

题目:

面试题35. 复杂链表的复制
138. 复制带随机指针的链表
面试题35. 复杂链表的复制
面试题35. 复杂链表的复制

题解:

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

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’两个链表,后者就是答案。

面试题35. 复杂链表的复制
注意:
node.next 是 node 复制出来的节点 ,node.random.next 也是 node.random 复制出来的节点。

2. 解释二:

  1. 输入如下图 [[1,2],[2,3],[3,null],[4,null]]
    面试题35. 复杂链表的复制
  2. 复制源节点。
    面试题35. 复杂链表的复制
  3. 生成克隆节点的 random 指针。
    面试题35. 复杂链表的复制
  4. 将原链表和克隆链表分离。
    面试题35. 复杂链表的复制
    实现的时候,谨记:源节点的 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. 图解 链表的深拷贝
  2. 复杂链表的复制-(看了绝对秒懂的思路)简单易懂的三步解决问题
  3. 利用哈希表,秒杀100%java
  4. 复制带随机指针的链表
  5. Java图解从HashMap到常数空间