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

朱雀 2022-11-20 10:57 183阅读 0赞

# 题目 #

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

示例 1：  
![在这里插入图片描述][2020102817082098.png_pic_center]

> 输入：head = \[\[7,null\],\[13,0\],\[11,4\],\[10,2\],\[1,0\]\]  
> 输出：\[\[7,null\],\[13,0\],\[11,4\],\[10,2\],\[1,0\]\]

示例 2：  
![在这里插入图片描述][20201028170906307.png_pic_center]

> 输入：head = \[\[1,1\],\[2,1\]\]  
> 输出：\[\[1,1\],\[2,1\]\]

示例 3：  
![在这里插入图片描述][20201028170945382.png_pic_center]

> 输入：head = \[\[3,null\],\[3,0\],\[3,null\]\]  
> 输出：\[\[3,null\],\[3,0\],\[3,null\]\]

示例 4：

> 输入：head = \[\]  
> 输出：\[\]  
> 解释：给定的链表为空（空指针），因此返回 null。

提示：

*  \-10000 <= Node.val <= 10000
 *  Node.random 为空（null）或指向链表中的节点。
 *  节点数目不超过 1000 。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof][https_leetcode-cn.com_problems_fu-za-lian-biao-de-fu-zhi-lcof]

# 解题思路 #

本题的意思其实就是实现一个链表的深度复制,这个链表的节点包含了next和random两个指针

使用原地算法,基本步骤分为三步:

*  简单复制一个新的节点,这一步只复制节点的val,并不复制节点的random,并把复制的节点放在原节点之后,比如原链表为1 -> 2 -> 3 -> null,复制后为1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ -> null
    
     *  创建一个节点new Node(val)
     *  复制节点的next指向原节点的next
     *  原节点的next指向复制节点
 *  完善复制节点的random指向的复制
 *  把复制的链表一分为二, 即复制链表为1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ -> null ,拆分为原链表1 -> 2 -> 3 -> null和复制链表1’ -> 2’ -> 3’ -> null
 *  返回复制链表即可

# 代码 #

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */
    class Solution { 
        public Node copyRandomList(Node head) { 
            // 特殊判断
            if (head == null) { 
                return null;
            }
    
            // 简单复制节点数据,并不复制节点的random
            // 1 -> 2 -> 3 -> null
            // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null 
            Node cur = head;
            while (cur != null) { 
                // 创建一个复制节点
                Node copyNode = new Node(cur.val);
                // 复制节点的next指向原节点的next
                copyNode.next = cur.next;
                // 原节点的next指向复制节点
                cur.next = copyNode;
                // 当前节点指针后移为复制直接的next
                cur = copyNode.next;
            }
    
            // 复制节点的random
            cur = head;
            while (cur != null) { 
                // 当前节点random指针不为空
                if (cur.random != null) { 
                    // 当前节点的下一个节点,也就是复制节点的random
                    // 指向当前节点的random指向的下一个节点,也就是复制节点
                    cur.next.random = cur.random.next;
                }
                // 指针后移
                cur = cur.next.next;
            }
    
            // 把链表一分为二,拆分成原链表和复制链表
            // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null 
            // 1 -> 2 -> 3 -> null
            // 1' -> 2' -> 3' -> null
            cur = head;
            // 复制链表的头结点
            Node newHead = head.next;
            Node copyCur = newHead;
            while (cur != null) { 
                // 指针后移
                cur.next = cur.next.next;
                cur = cur.next;
                // 判断复制节点的下一个节点是否为空
                if (copyCur.next != null) { 
                    // 指针后移
                    copyCur.next = copyCur.next.next;
                    copyCur = copyCur.next;
                }
            }
            return newHead;
        }
    }

# 复杂度 #

*  时间复杂度:O(n),循环迭代链表3n次
 *  空间复杂度:O(1),额外指针占用常数级额外空间

[2020102817082098.png_pic_center]: /images/20221120/c05e627c58e44b5497b0c2a36b7aee18.png
[20201028170906307.png_pic_center]: /images/20221120/522d24fd376040c2920e9f7146ca91a7.png
[20201028170945382.png_pic_center]: https://img-blog.csdnimg.cn/20201028170945382.png#pic_center
[https_leetcode-cn.com_problems_fu-za-lian-biao-de-fu-zhi-lcof]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof