Txing

欢迎来到 | 伽蓝之堂

0%

JZOffer 35 复杂链表的复制-中等-链表

Posted on In
Symbols count in article: 2.8k Reading time ≈ 3 mins.
JZOffer 35 复杂链表的复制-中等-链表

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

Question

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

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

提示：

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

本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

Approach 1: 深度优先搜索

图的基本单元是 顶点，顶点之间的关联关系称为 边，我们可以将此链表看成一个图。由于图的遍历方式有深度优先搜索和广度优先搜索，同样地，对于此链表也可以使用深度优先搜索和广度优先搜索两种方法进行遍历。

  • 从头结点 head 开始拷贝；
  • 由于一个结点可能被多个指针指到，因此如果该结点已被拷贝，则不需要重复拷贝；
  • 如果还没拷贝该结点，则创建一个新的结点进行拷贝，并将拷贝过的结点保存在哈希表中；
  • 使用递归拷贝所有的 next 结点，再递归拷贝所有的 random 结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def copyRandomList(self, head) :
        def dfs(head):
            if not head: return None # 判断遍历链表结束
            if head in visited: # 结点已存在，返回结点避免重复复制
                return visited[head]

            copy = Node(head.val, None, None) # 创建新结点
            visited[head] = copy # hash中增加一个结点
            copy.next = dfs(head.next)
            copy.random = dfs(head.random)
            return copy

        visited = {} # 创建存放结点的链表
        return dfs(head) # 最后返回头指针

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的节点数量。
  • 空间复杂度：O(n）。

Approach 2: 广度有限搜索

  • 创建哈希表保存已拷贝结点，格式 {原结点：拷贝结点}
  • 创建队列，并将头结点入队；
  • 当队列不为空时，弹出一个结点，如果该结点的 next 结点未被拷贝过，则拷贝 next 结点并加入队列；同理，如果该结点的 random 结点未被拷贝过，则拷贝 random 结点并加入队列；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def copyRandomList1(self, head: 'Node') -> 'Node':
        visited = {}

        def bfs(head):
            if not head: return head # 判断遍历链表结束
            clone = Node(head.val, None, None) # 创建新结点
            queue = collections.deque() # 双端数列
            queue.append(head)
            visited[head] = clone # 结点存入hash
            while queue:
                tmp = queue.pop() #
                if tmp.next and tmp.next not in visited: # .next结点非空且未复制
                    visited[tmp.next] = Node(tmp.next.val, [], [])
                    queue.append(tmp.next)
                if tmp.random and tmp.random not in visited: # .random结点非空且未复制
                    visited[tmp.random] = Node(tmp.random.val, [], [])
                    queue.append(tmp.random)
                visited[tmp].next = visited.get(tmp.next) # 字典get()函数返回指定键的值
                visited[tmp].random = visited.get(tmp.random)
            return clone # 返回头指针
        return bfs(head)

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的节点数量。
  • 空间复杂度：O(n）。

Approach 3: 迭代

该方法的思路比较直接，对于一个结点，分别拷贝此结点、next 指针指向的结点、random 指针指向的结点， 然后进行下一个结点...如果遇到已经出现的结点，那么我们不用拷贝该结点，只需将 next 或 random 指针指向该结点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        cur = head
        while cur:
            new_node = Node(cur.val,None,None)   # 克隆新结点
            new_node.next = cur.next
            cur.next = new_node   # 克隆新结点在cur 后面
            cur = new_node.next   # 移动到下一个要克隆的点
        cur = head

        while cur:  # 链接random
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next

        cur_old_list = head # 将两个链表分开
        cur_new_list = head.next
        new_head = head.next
        while cur_old_list:
            cur_old_list.next = cur_old_list.next.next
            cur_new_list.next = cur_new_list.next.next if cur_new_list.next else None
            cur_old_list = cur_old_list.next
            cur_new_list = cur_new_list.next
        return new_head

复杂度分析

  • 时间复杂度：O(N) 。 空间复杂度：O(1) 。

总结 在对链表进行操作的时候，经常要记得把一个结点的指针域用另一个指针保存起来，这样返回的时候不容易出错。