资讯专栏INFORMATION COLUMN

LeetCode 138:复制带随机指针的链表 Copy List with Random Poin

entner / 2196人阅读

摘要:给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为,空间复杂度为。

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

示例:

输入:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。

提示:

你必须返回给定头的拷贝作为对克隆列表的引用。

Note:

You must return the copy of the given head as a reference to the cloned list.

解题思路:

由于需要考虑随机指针,随机指针指向的节点可能是null,也可能是链表的最后一个节点,深拷贝下,你不能将新链表的随机指针指向原链表的节点,所以无法一遍得到新链表。

两种解题方法,一种是拷贝所有节点,暂存在一种数据结构内,然后再遍历一遍该数据结构,找到拷贝的节点,确定随机指针的指向。因为每个节点都要找到随机指针指向的节点,如果借助 散列表(字典) 其查找复杂度为 O(1) ,这样可以把总时间复杂度降到 O(n) ,由于要暂存所有节点,其空间复杂度为 O(n)。

另一种解题方法是需要三次遍历得到结果,简单来说就是先把每个节点拷贝,并把拷贝节点连接到原节点后面,依次类推。确定随机节点的关系之后再拆分链表。是一种很巧妙的思路:

原链表:1->2->3
复制每个节点到原节点后面:1->1->2->2->3->3
复制随机指针的指向关系
拆分链表:1->2->3, 1->2->3

复制随机指针指向时,原节点的随机节点下一个节点即为新节点的随机节点。假如原链表:1->2->3,节点1的随机节点为3,复制节点之后:1->1->2->2->3->3

我们只需将新节点(原节点1的后一个节点1)指向原节点的随机节点的后一个节点(原节点的随机节点为3,而复制之后随机节点3的后一个节点依然为3,但这个节点为新节点),最后拆分链表(链表拆分不影响节点指向关系)。其时间复杂度为 O(n),空间复杂度为 O(1)。

第一种方法:

Java:

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap map = new HashMap<>();//借助hashMap
        Node newHead = new Node(0);//虚拟头节点
        Node cur = newHead;//指针指向当前节点
        Node tmp;
        while (head != null) {
            if (map.containsKey(head)) {//查询原节点是否已存在于map
                tmp = map.get(head);//如果存在直接取value值
            } else {
                tmp = new Node(head.val);//不存在则新建一个值相同的节点
                map.put(head, tmp);//存入map,key为原节点,value为新节点
            }
            cur.next = tmp;
            if (head.random != null) {//原节点的随机节点不为空的情况下
                if (map.containsKey(head.random)) {//查询该随即节点是否已存在于map
                    tmp.random = map.get(head.random);//存在则直接将新节点的随机指针指向其value值
                } else {
                    tmp.random = new Node(head.random.val);//不存在则新建一个值相同的随机节点
                    map.put(head.random, tmp.random);//存入map,key为原节点的随机节点,value为新节点的随机节点
                }
            }
            head = head.next;//刷新原链表当前头节点
            cur = tmp;//即cur=cur.next,刷新新链表当前节点
        }
        return newHead.next;
    }
}

Python3:

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        if not head: return None
        map = {}
        newHead = Node(val=0, next=None, random=None)
        cur = newHead
        while head:
            if head in map.keys():
                tmp = map.get(head)
            else:
                tmp = Node(val=head.val, next=None, random=None)
                map.setdefault(head, tmp)
            cur.next = tmp
            if head.random:
                if head.random in map.keys():
                    tmp.random = map.get(head.random)
                else:
                    tmp.random = Node(val=head.random.val, next=None, random=None)
                    map.setdefault(head.random, tmp.random)
            head = head.next
            cur = tmp
        return newHead.next
第二种方法:

Java:

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        //复制节点 1->2->3 ==> 1->1->1->2->2->3->3
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            Node tmp = new Node(cur.val);
            cur.next = tmp;
            tmp.next = next;
            cur = next;
        }
        //复制随机指针
        cur = head;
        while (cur != null) {
            //cur.next.random=>新节点的随机节点     cur.random.next=>原节点的随机节点的下一个节点
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;//链表扩展一倍后肯定是偶数位链表,所以可以直接用cur.next.next
        }
        //分离节点
        cur = head;
        Node newHead = head.next;//新链表头节点
        while (cur != null) {
            Node tmp = cur.next;
            cur.next = tmp.next;
            cur = cur.next;
            tmp.next = cur == null ? null : cur.next;
        }
        return newHead;
    }
}

Python3:

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        if not head: return None
        cur = head
        while cur:
            next = cur.next
            tmp = Node(val=cur.val, next=next, random=None)
            cur.next = tmp
            cur = next
        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next
        cur = head
        newHead = head.next
        while cur:
            tmp = cur.next
            cur.next = tmp.next
            cur = cur.next
            tmp.next = cur.next if cur else None
        return newHead

欢迎关注微.信公.众号一起学习:爱写Bug

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/75626.html

相关文章

  • LeetCode 138复制随机指针链表 Copy List with Random Poin

    摘要:给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为,空间复杂度为。 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 A linked list is g...

    Lucky_Boy 评论0 收藏0
  • leetcode138. Copy List with Random Pointer

    摘要:题目要求假设存在这样一个链表,在链表的每一个节点中,除了记录了自身值和指向下一个节点的指针,还有一个随机指针指向链表中任意一个节点。所以可以在两次遍历后完成任务。最后一圈遍历,我们调整指针,恢复原链表和塑造新链表。 题目要求 A linked list is given such that each node contains an additional random pointer ...

    Kross 评论0 收藏0
  • 【数据结构】链表经典算法题集锦

    摘要:前言本章将分享十一道来自牛客网中的经典链表算法题来介绍数据结构中链表在算法题中的应用。注意,函数返回结果后,链表必须保持其原始结构。 前言:本章将分享十一道来自Le...

    Ashin 评论0 收藏0
  • LeetCode 133:克隆图 Clone Graph

    摘要:解题思路涉及到图的遍历无非就是深度优先搜索广度优先搜索,可以先看前几日的这篇文章就需要借助队列实现,可以借助栈也可以直接用递归实现。 题目: 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。 Given a reference of a node in a connected undirec...

    Simon 评论0 收藏0
  • [Leetcode] Copy List with Random Pointer 复制随机指针

    摘要:栈迭代复杂度时间空间如果不算新链表的空间则是思路由于随机指针有可能产生环路,我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着指针直接复制,因为我们不知道随机指针所指向的新节点是哪个。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

    Olivia 评论0 收藏0

发表评论

0条评论

entner

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<