-
2021-12-04 19:31:29
复制链表
# 定义结点 class Node(): def __init__(self,item): self.val = item self.next = None def copyList(head): cur = head # 当前节点 dum = pre = Node(0) # 复制新链表的起点 while cur: node = Node(cur.val) # 复制链表的第一个节点 pre.next = node # 让新链表的起点指向 第一个节点 cur = cur.next # 旧链表下一个节点 pre = node # 新链表下一个节点 return dum.next # 返回新链表的起点 if __name__ == "__main__": # 定义一个链表: a -> b -> c a = Node(5) b = Node(4) c = Node(3) a.next = b b.next = c new_list = copyList(a) print(new_list.val) print(new_list.next.val) print(new_list.next.next.val)
更多相关内容 -
两两认识leetcode-copy-list-with-random-pointer:使用随机指针复制链表
2021-06-30 22:05:46使用随机指针复制链表 给出一个链表,使得每个节点都包含一个额外的随机指针,该指针可以指向链表中的任何节点或为空。 返回列表的深层副本。 链表在输入/输出中表示为 n 个节点的列表。 每个节点都表示为一对 [val,... -
C语言之复杂链表的复制方法(图示详解)
2020-08-30 01:58:02下面小编就为大家带来一篇C语言之复杂链表的复制方法(图示详解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧 -
(python version) 劍指offer 35. 复制链表的复制
2020-07-01 18:19:13题目描述 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random ...第二步:设置复制链表上的 m_psibling 。如果原始链表节点N的 m_psibling 指题目描述
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
来源:力扣(LeetCode)
解题思路
剑指书上的方法
1.方法一
- 第一步:复制原始链表上的每个节点N、创造N’ ; 把创造出来的节点用 m_pnext链接起来; 把<N,N’>放进哈希表。
- 第二步:设置复制链表上的
m_psibling
。如果原始链表节点N的 m_psibling 指向节点S; 复制链表当中的 N’ 指向 S’ 。
2.方法二
- 第一步:复制链表的节点,将复制的节点接到原始节点的后面
e.g. 1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ - 第二步:将链表复制节点的 random 指向的指针 (n.next.random),指向原始节点的后面 (n.random.next)
Leetcode上的方法
- 题意的复制是指『深拷贝』(Deep Copy)<=> 浅拷贝(Shallow Copy)
- 浅拷贝只复制了某个对象的指针,而不复制对象本身,共享同一块内存。 => newhead = head (这只是将指针指到了 head)
- 深拷贝要创造一个一模一样的对象,新对象跟旧对象不共享内存,修改新对象不会改到原对象。
- 用 DFS(Depth-First Search)的递归解法
- 将已经存在的节点存入 Hash Table。
- 从最深的一个节点开始复制。
- 在写逻辑的时候,思考最后一步的要件(判断逻辑 & 返回),递归解法都是如此操作。
Python代码
""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: 'Node') -> 'Node': """ 剑指方法二 """ if not head: return None n = head # next指针:1->1'->2->2'->3->3' while n: node = Node(n.val) node.next = n.next n.next = node n = node.next # random指针 n = head while n: if not n.random: n.next.random = None else: n.next.random = n.random.next # 这边是回到原始n链表的随机的下一个复制的点 n = n.next.next # 跨号返回 n = head.next while n.next: n.next = n.next.next n = n.next return head.next """ Leetcode方法:用DFS解 """ def dfs(head): if not head: return None if head in visited: return visited[head] # Deep Copy:创建复制的新节点 copy = Node(head.val) visited[head] = copy copy.next = dfs(head.next) copy.random = dfs(head.random) return copy visited = {} return dfs(head)
-
复制链表
2011-09-13 22:52:07题目:已知一链表,每个节点...这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样...题目:已知一链表,每个节点除了有一个指向下一节点的指针外,还有一随机指针指向链表中的任意节点(可能为空,也有可能为自身),请复制一个链表,要求节点的顺序以及节点上的随机指针指向的节点位置和原链表一致。
这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样。
typedef struct Node { int nData; Node* pNext; Node* pRandom; } Node; Node* DuplicateList(Node* pSrcListHead) { if (pSrcListHead == NULL) return NULL; Node* pNode = pSrcListHead; while (pNode != NULL) { Node* pNewNode = new Node; pNewNode->nData = pNode->nData; pNewNode->pNext = pNode->pNext; pNewNode->pRandom = pNode->pRandom; pNode->pNext = pNewNode; pNode = pNewNode->pNext; } Node* pDestListHead = pSrcListHead->pNext; pNode = pSrcListHead; while (pNode != NULL) { pNode->pNext->pRandom = pNode->pRandom->pNext; pNode = pNode->pNext->pNext; } pNode = pSrcListHead; Node* pNode2 = pNode->pNext; while (pNode != NULL) { pNode->pNext = pNode2->pNext; pNode = pNode->pNext; if (pNode) pNode2->pNext = pNode->pNext; else pNode2->pNext = NULL; pNode2 = pNode2->pNext; } return pDestListHead; }
不过目前还未考虑到原始链表有环的情况,如果原始链表有环,则应该先求出环的入口点,然后利用上面的方法进行链表复制。
原文地址:http://hi.baidu.com/%B3%A3%D1%C5%C3%F4/blog/item/173d50ae523a0ede7dd92a63.html
-
【剑指Offer】25.复杂链表的复制(Python实现)
2020-12-22 09:20:41输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会... -
JAVA练习54-复杂链表的复制
2022-01-27 15:15:22请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。 示例 1: 输入:head = [[7,null],[13,0],...请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2:
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]示例 3:
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]示例 4:
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。提示:
- -10000 <= Node.val <= 10000
- Node.random 为空(null)或指向链表中的节点。
- 节点数目不超过 1000 。
分析:
方法1:哈希表
该题的难点在于 random 指针的复制,因为 random 指针可能会指向前面的节点,因此我们可以定义一个哈希表来存储复制的节点,键为旧节点,值为新节点,第一次遍历先复制链表的节点,第二次遍历复制链表的指针。
时间复杂度:O(n)
空间复杂度:O(n)/* // 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) { //创建哈希表 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 node = map.get(cur); //复制 next 和 random 指针 node.next = map.getOrDefault(cur.next, null); node.random = map.getOrDefault(cur.random, null); //继续遍历下一个节点 cur = cur.next; } //返回对应复制的节点,头节点为空时返回空 return map.getOrDefault(head, null); } }
方法2:拼装+拆分
方法1 虽然实现起来较为简单,但面试的时候还是喜欢考验在原链表上进行操作,且空间复杂度较小,因此我们可以用到拼装的方法,在每个节点之间复制一个新的节点,拿 head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 举例:
- 旧链表: 7 → 13 → 11 → 10 → 1
- 拼装链表:7 → 7* → 13 → 13* → 11 → 11* → 10 → 10* → 1 → 1*
这样就得一个拼装的链表,这样的链表满足一个特性,原链表节点(node)的 next 是指向新复制的一个节点的,因此新节点的 random 指针可以指向旧节点 random 指针的 next,即:node.next.random = node.random.next,这样就可以实现 random 的复制操作。
最后,我们再将拼装链表拆分回旧链表和新复制的链表即可,拆分可以用 node.next = node.next.next,但是注意旧链表的操作一定要在新链表之前,并且要把最后一个节点的指针指向空,因为本来指的新节点。
时间复杂度:O(n)
空间复杂度:O(1)/* // 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; } //第一次遍历,复制并拼接新节点 for(Node node = head; node != null; node = node.next.next){ //复制节点 Node next = new Node(node.val); //拼接 next.next = node.next; node.next = next; } //第二次遍历,复制 random for(Node node = head; node != null; node = node.next.next){ if(node.random != null){ node.next.random = node.random.next; } } //定义新旧节点 Node cur = head.next, pre = head, ans = cur; //第三次遍历,将缝合链表拆分成旧链表和新链表 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; } }
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof -
复制链表的复制
2017-08-05 23:03:39题目:/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {...*/输入一个复杂链表(每个节点中有节点值,以及两个指针, -
剑指offer~复杂链表的复制(Java)
2021-01-20 03:02:45首先,参数为一个pHead,要求我们能够复制链表。 我们先来看看其他大佬的做法(转自牛友chancy) 逻辑很强,值得学习。 /* *解题思路: *1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面; *2... -
Java复杂链表的复制
2022-05-08 20:15:31复杂链表的复制 class Solution { public Node copyRandomList(Node head) { if(head == null){ return null; } //使cur指向原链表的头节点 Node cur = head; //创建哈希表 //<原链表节点, 新的链表... -
C语言之复杂链表的复制(图示详解)
2021-05-22 14:31:08什么是复杂链表?复杂链表指的是一个链表...今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。复杂链表的数据结构如下:1 typedef int DataType; //数据域的类型23 //复杂链表的数据结构45 typede... -
复杂链表的复制 -- java
2021-11-16 12:45:48请实现函数,用于复制一个复杂链表。在复杂链表中,每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意结点或者NULL。 复杂链表如下图: 复杂节点定义如下: public class ... -
【链表】复杂链表的复制
2021-02-03 21:40:13输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用... -
复杂链表的复制
2020-07-03 11:34:21输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个指向链表中任意一个节点或NULL),返回结果为复制后复杂链表的head。 节点结构: class Node { public: Node(int _val)//构造... -
C++算法(七)复杂链表的复制
2022-02-28 17:09:47借助vector和map容器实现链表复制 -
链表复制(包含进阶) C++
2021-03-17 20:02:33key放原来链表的结点 X ,value放复制之后的结点 X’ 。 遍历哈希表,或者原来的链表。 找到 X 结点的next结点 Y ,再通过map找到复制之后的结点 Y‘ 。 将 X’ 的next指针指向 Y‘ 。 rand指针也一样操作。 重复... -
复制链表的复制深拷贝
2021-01-13 20:48:27题目 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next ...第三步,将链表剥离,恢复原链表,并产生复制链表。 代码 /* // Definition for a Node. class Node { int val; No -
Java实现复杂链表的复制
2022-01-30 21:37:17Java实现复杂链表的复制 过程很简单,直接上代码 import java.util.HashMap; import java.util.Map; public class Solution { /** * 复杂链表复制 * @param pHead * @return */ public RandomListNode ... -
剑指Offer:[第2天 链表(简单)]--->复杂链表的复制
2022-02-16 20:53:24请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。 示例1: 输入:head = [[7,null],[13,0],[11,4... -
【剑指offer】复杂链表的复制(详解 + 两种方法)
2020-05-21 13:27:14【剑指offer】复杂链表的复制 【本题链接】 【题目描述】 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝... -
LeetCode 138. 复制带随机指针的链表(Map,复制链表,Java)
2021-07-26 11:30:00新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如,如果原链表中有 X 和 Y 两个节点 -
复杂链表的复制(C++解法)
2022-03-15 22:06:09复杂链表的复制(C++解法) 描述 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,... -
java 复杂链表的复制
2020-08-30 16:06:20输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序... -
35. 复杂链表的复制
2022-02-26 11:03:41请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。 示例 1: 输入:head = [[7,nu... -
golang力扣leetcode 38.复制带随机指针的链表
2021-12-03 18:24:0938.复制带随机指针的链表38.复制带随机指针的链表题解代码 38.复制带随机指针的链表 38.复制带随机指针的链表 题解 思路: 复制节点,紧挨到到后面,1->2->3 ==> 1->1’->2->2’->3->3’ ... -
剑指offer:Python 复杂链表的复制 图解 实现过程
2019-11-16 15:29:56详细加图解完成:“复杂链表的复制” -
LeetCode第138题—复制带随机指针的链表—Python实现
2021-07-04 11:07:14LeetCode第138题—复制带随机指针的链表 自己代码的开源仓库:click here 欢迎Star和Fork ???? 题目描述 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空... -
剑指 Offer 35. 复杂链表的复制 为什么不能直接复制?
2021-03-25 19:21:19这里主要反思一下为什么不能直接复制,所谓的直接复制就是新定义一个节点,然后直接把原链表的值、next、random直接复制到新的链表后面接着,这样会导致一个问题,首先这里是指针的复制,所以直接复制的是地址,那么... -
复杂链表的复制(python)
2020-06-11 16:47:01输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用... -
《剑指Offer》——链表的简单应用 链表节点的转换 与 链表的复杂复制 链表的题多设置几个标志节点处理就...
2022-01-24 11:58:01本篇内容:链表反转与复制(简单) 文章专栏:《剑指offer》 面试高频数据结构与算法 最近更新:2022年1月21日 《剑指Offer》——栈与队列简单应用 如果遇到栈与队列的相关问题不妨多来个辅助栈 个人简介:一只二本...