前景回顾:我们用 环形链表的方法巧妙解决了约瑟夫问题 可是链表就到处为止了吗？当然不是 下面带给大家两道我刷过较为经典的算法题 两道面试的真题 一道是tx 一道阿里的
腾讯面试题：复制随机节点
题目说明：
给定一个链表，每个节点包含一个指向任意节点的随机指针，同时每个节点有一个指向同一链表中节点的指针，输出这个链表的深拷贝。
输入示例：
代码语言：javascript复制输入：
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个排序链表
题目说明：
给你一个链表数组，每个链表都已经按升序排列，请你将所有的链表合并到一个升序链表中，返回合并后的链表。
代码语言：javascript复制复制代码
输入：
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
返回头节点： 1import 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
