侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

35 复杂链表的复制

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 106 阅读 / 2,701 字 / 正在检测是否收录...

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

方法一:哈希表

遍历链表,根据就节点 $oldNode$,创建新节点 $newNode$,然后使用哈希表保存新旧节点的映射关系 $<oldNode , newNode >$。在遍历一次原始链表,当遍历到每个节点时,执行以下操作

  • 根据 $oldNode$ 从哈希表中拿到对应的 $newNode$ ,拼接到新链表中。
  • 根据 $oldNode.random$ 从哈希表中拿到 $newNode$ 对应的 $random$ 指针应该指向的节点。
public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    // 用哈希表先建立每个旧节点与新节点的映射
    HashMap<Node, Node> map = new HashMap<>();
    Node cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    cur = head;
    while (cur != null) {
        Node newCur = map.get(cur);
        // 找新节点的 next 和 random,它们都应该在 map 中
        // 且各自与 cur.next 和 cur.random 对应
        newCur.next = map.get(cur.next);
        newCur.random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}

复杂度分析

  • 时间复杂度$O(N)$:$N$ 为链表的节点个数。哈希表的插入与搜索都是 $O(1)$ 时间的,链表的拼接也是 $O(1)$ 的。
  • 空间复杂度$O(N)$:$N$ 为链表的节点个数。哈希表需要存储全部的节点。

方法二:拼接+拆分

拼接

先把新旧链表连接在同一个链表上,或者可以理解为在旧的节点后面跟着一个新的节点,新结点值等于旧的结点值,如下图中的第 $2$ 步。然后遍历拼接后的链表,找到新节点的 $random$ 指针,如下图中的第 $3$ 步

35-拼接链表

拆分

然后遍历拼接后的链表,进行拆分操作。使用双指针,$cur$ 指针指向 $head.next$,$pre$ 作为 $cur$的前驱节点指向 $head$。接下来就是 $cur$ 和 $pre$ 的 $next$ 指针都是两步走,$cur.next = cur.next.next$ 。直到 $cur$ 指针走到尾部,就结束了。

35-拆分链表

代码:

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node cur = head;
    // 先把新旧链表连接在同一个链表上
    // 或者可以理解为在旧的节点后面跟着一个新的节点,新结点值等于旧的结点值
    // 比如:
    // 1->2->3
    // 1->1->2->2->3->3
    while (cur != null) {
        Node newNode = new Node(cur.val);
        newNode.next = cur.next;
        cur.next = newNode;
        cur = newNode.next;
    }
    cur = head;
    // 找到新节点的 random 节点
    while (cur != null) {
        if (cur.random != null) {
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }
    // 拆分链表
    cur = head.next;
    Node ans = head.next;
    Node pre = head;
    while (cur.next != null) {
        pre.next = pre.next.next;
        cur.next = cur.next.next;
        pre = pre.next;
        cur = cur.next;
    }
    // 处理原链表的尾结点
    pre.next = null;
    return ans;
}

复杂度分析

  • 时间复杂度$O(N)$:$N$ 为链表的节点数目,算法中需要进行三次链表遍历,每一次占用 $O(N)$ 时间,循环中的操作占用 $O(1)$ 时间。
  • 空间复杂度$O(1)$:算法中使用的变量据占用 $O(1)$ 空间。
0

评论区