厦门网站建设外包/企业seo服务
目录
- 1、题目描述:
- 2、方法一:迭代+哈希表
- 思路:
- 代码:
- 3、方法二:后继节点
- 思路:
- 代码:
- 4、总结
1、题目描述:
2、方法一:迭代+哈希表
思路:
我们先看看暴力法怎么做的:
看到这道题之后,很多人的第一反应是把复制分成两步:第一步是复制原始链表上的每一个节点,并用nextnextnext给链接起来;第二步是设置每个节点的randomrandomrandom指针。
第二步的具体做法如下:假设原始链表中的某个节点NNN的randomrandomrandom指针指向节点SSS,由于SSS在链表中可能在NNN的前面也可能在NNN的后面,所以要定位SSS的位置需要从原始链表的头节点开始找。如果从原始链表的头节点开始沿着nextnextnext经过sss步找到节点SSS,那么在复制链表上节点的N′N'N′的randomrandomrandom(记为S′S'S′)离复制链表的头节点的距离也是沿着nextnextnext指针sss步。用这种办法就可以为复制链表上的每个节点设置randomrandomrandom指针。
对于一个含有nnn个节点的链表,由于定位每个节点的randomrandomrandom都需要从链表头节点开始经过O(n)O(n)O(n)步才能找到,因此这种方法总的时间复杂度是O(n2)O(n^2)O(n2)。
我们看看迭代+哈希表咋做的:
上述方法的时间主要花费在定位节点randomrandomrandom上,这个是可以改进的,也就是说,我们可以事先把创建出来的节点N′N'N′与原始的NNN节点保存在哈希表中,即<N:N′><N:N'><N:N′>。如果在原始链表中节点NNN的randomrandomrandom指向节点SSS,那么在复制链表中,对应的N′N'N′应该指向S′S'S′,由于有了哈希表,我们可以用O(1)O(1)O(1)的时间根据SSS找到S′S'S′。
代码在具体实现的时候,先遍历原始链表,创建字典对<N:N′><N:N'><N:N′>;然后再遍历一遍原始链表,用于给新链表设置nextnextnext和randomrandomrandom指针。
代码:
"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""
class Solution:def copyRandomList(self, head: 'Node') -> 'Node':"""迭代+哈希表"""if head == None: return headnode_map = {}cur = head# 1.存储新旧节点对while cur:node_map[cur] = Node(cur.val) # 创建字典对,原始节点一定为keycur = cur.next# 2.给新链表设置next和random指针cur = headwhile cur:if cur.next: # 防止字典key为Nonenode_map[cur].next = node_map[cur.next] # 设置nextif cur.random: # 同上node_map[cur].random = node_map[cur.random] # 设置randomcur = cur.nextreturn node_map[head] # 返回新链表的头节点
3、方法二:后继节点
思路:
注意到方法一需要使用哈希表记录每一个节点对应新节点的创建情况,而我们可以使用一个小技巧来省去哈希表的空间。
我们首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表:A→B→CA→B→CA→B→C我们可以将其拆分为: A→A′→B→B′→C→C′A→A′→B→B′→C→C′A→A′→B→B′→C→C′
对于任意一个原节点 SSS,其拷贝节点 S′S'S′ 即为其后继节点。
这样,我们可以直接找到每一个拷贝节点 S′S'S′的随机指针应当指向的节点,即为其原节点 SSS 的随机指针指向的节点 TTT 的后继节点 T′T'T′ 。
需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。
当我们完成了拷贝节点的随机指针的赋值,我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。
代码:
"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""
class Solution:def copyRandomList(self, head: 'Node') -> 'Node':"""后继节点"""if head == None: return head# 1.先把链表A->B->C转换成A->A'->B->B'->C->C'cur = headwhile cur:next = cur.next # 存储Bnew_node = Node(cur.val) # 定义A'cur.next = new_node # A->A'new_node.next = next # A'->Bcur = next # 指针指向B# 2.给每一个新节点设置random指针cur = headwhile cur:if cur.random:cur.next.random = cur.random.next # 下一个新节点的random,就是原节点random的下一个cur = cur.next.next# 3.将A->A'->B->B'->C->C'拆分开cur = head.next # 从A'开始遍历head2 = cur # 把新链表的头给保存,用于返回while cur.next: # 注意这个cur.next,一旦这个存在,则一定存在cur.next.next,看链表就知道为啥cur.next = cur.next.next # A'->B'cur = cur.next # 当前遍历的节点指向B'return head2
4、总结
做链表的题,建议画一个链表的例子,然后看指针指向,例如上面的例子:A→A′→B→B′→C→C′A→A′→B→B′→C→C′A→A′→B→B′→C→C′看着这个敲代码,就不会把自己绕进去了。