腾讯面试题：复制随机节点
题目说明：
给定一个链表，每个节点包含一个指向任意节点的随机指针，同时每个节点有一个指向同一链表中节点的指针，输出这个链表的深拷贝。
输入示例：
输入： Node* p = new Node(p1); p1 = new Node(p2); p2 = new Node(p3); p3 = new Node(null); // 随机连接 p->random = p2; p1->random = null; p2->random = p3; Node* clone = cloneRandomNode(p);
输出示例：
返回与原链表相同结构的复制链表，并正确设置每个节点的随机指针。
时间复杂度：O(n)
- 其中 n 是链表的长度，我们需要遍历整个链表一次来创建复制品。
空间复杂度：O(n)
- 存储复制的节点需要额外的空间。
解析
题目分析：
这个问题要求我们复制一个链表，其中每个节点包含一个指向任意节点的随机指针。我们需要返回这个链表的深拷贝，并正确设置每个节点的随机指针。
解题过程：
- 首先，我们遍历原始链表，对于每个节点，创建一个新节点，并将其插入到原节点的后面。这样我们就可以同时访问原始节点和新节点。例如，原始链表为
1 -> 2 -> 3，复制后变为1 -> 1' -> 2 -> 2' -> 3 -> 3'。
原始链表： 1 -> 2 -> 3 复制后的链表： 1' -> 2' -> 3'
- 然后，我们再次遍历链表，这次是为了设置每个新节点的随机指针。我们根据原节点的随机指针找到对应的新节点，并将其设置为新节点的随机指针。例如，如果原节点
2的随机指针指向3，那么新节点2'的随机指针应该指向3'。
原始链表： 1 -> 2 -> 3 复制后的链表： 1' -> 2' -> 3' 随机指针： N -> 2 -> N 复制后的随机指针： N -> 2' -> N
- 最后，我们将新旧节点分离，并返回复制链表的头节点。例如，将
1 -> 1' -> 2 -> 2' -> 3 -> 3'分离成1 -> 2 -> 3和1' -> 2' -> 3'，然后返回1'作为复制链表的头节点。
原始链表： 1 -> 2 -> 3 复制后的链表： 1' -> 2' -> 3' 分离后的链表： 1 -> 2 -> 3 分离后的复制链表： 1' -> 2' -> 3' 返回头节点： 1'
class Node: def __init__(self, val=0, next=None, random=None): self.val = val self.next = next self.random = random def cloneRandomNode(head): if not head: return None # 第一步：复制每个节点，并将新节点插入原节点后面 curr = head while curr: new_node = Node(curr.val) new_node.next = curr.next curr.next = new_node curr = new_node.next # 第二步：设置每个新节点的随机指针 curr = head while curr: curr.next.random = curr.random.next if curr.random else None curr = curr.next.next # 第三步：分离新旧节点，返回复制链表的头节点 curr = head new_head = head.next while curr: next_old = curr.next next_new = curr.next.next curr.next = next_new if next_new: curr.next.next = next_old curr = next_old return new_head
阿里巴巴面试题：合并K个排序链表
题目说明：
给你一个链表数组，每个链表都已经按升序排列，请你将所有的链表合并到一个升序链表中，返回合并后的链表。
复制代码 输入： lists = [[1,4,5],[1,3,4],[2,6]]
输出示例：
输出：[1,1,2,3,4,4,5,6]
时间复杂度：O(N*log(k))
- 其中 N 是所有链表中元素的总数，k 是链表的个数。假设使用最小堆处理每个链表的头部元素。
空间复杂度：O(k)
- 存储 k 个链表头部节点所需的空间。
解析
题目分析：
这个问题要求我们合并 k 个已排序的链表，并返回一个新的升序链表。我们可以使用分治法来解决这个问题。
解题过程：
- 我们使用最小堆来存储每个链表的头部节点。这样可以快速地找到当前最小的节点。例如，如果有三个链表分别为
1 -> 4 -> 5、1 -> 3 -> 4和2 -> 6，则最小堆中的元素为(1, node1)、(1, node2)和(2, node3)。
链表1: 1 -> 4 -> 5 链表2: 1 -> 3 -> 4 链表3: 2 -> 6 最小堆： (1, node1), (1, node2), (2, node3)
- 我们创建一个虚拟头节点 dummy，用于连接所有合并后的节点。
- 我们不断从最小堆中取出最小的节点，将其连接到结果链表中，并将该节点的下一个节点加入堆中，直到堆为空。例如，我们从最小堆中取出 (1, node1)，将其连接到结果链表中，然后将 node1.next（即值为 4 的节点）加入堆中。
结果链表： dummy -> 1 最小堆： (1, node2), (4, node4), (6, node6)
- 最后，我们返回合并后链表的头节点。例如，最终的结果链表为
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6，返回dummy.next。
结果链表： 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 返回头节点： 1
import heapq from typing import List, Optional class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]: if not lists: return None # 使用最小堆来存储每个链表的头部节点 min_heap = [] for node in lists: if node: heapq.heappush(min_heap, (node.val, node)) dummy = ListNode() current = dummy # 每次从堆中取出最小的节点，将其连接到结果链表中，并将该节点的下一个节点加入堆中 while min_heap: val, node = heapq.heappop(min_heap) current.next = ListNode(val) current = current.next if node.next: heapq.heappush(min_heap, (node.next.val, node.next)) return dummy.next
