【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解
🎉🎉欢迎光临🎉🎉
🏅我是苏泽，一位对技术充满热情的探索者和分享者。🚀🚀
🌟特别推荐给大家我的最新专栏《Spring 狂野之旅：底层原理高级进阶》 🚀《数据结构与算法：初学者入门指南》📘📘《Spring 狂野之旅：底层原理高级进阶》 🚀
本专栏纯属为爱发电永久免费！！！
这是苏泽的个人主页可以看到我其他的内容哦👇👇
努力的苏泽
http://suzee.blog.csdn.net/
前景回顾:我们用 环形链表的方法巧妙解决了约瑟夫问题 可是链表就到处为止了吗？当然不是 下面带给大家两道我刷过较为经典的算法题 两道面试的真题 一道是tx 一道阿里的
目录
腾讯面试题：复制随机节点
题目说明：
输入示例：
输出示例：
时间复杂度：O(n)
空间复杂度：O(n)
解析
题目分析：
解题过程：
阿里巴巴面试题：合并K个排序链表
题目说明：
输出示例：
时间复杂度：O(N*log(k))
空间复杂度：O(k)
解析
题目分析：
解题过程：
腾讯面试题：复制随机节点
题目说明：
给定一个链表，每个节点包含一个指向任意节点的随机指针，同时每个节点有一个指向同一链表中节点的指针，输出这个链表的深拷贝。
输入示例：
输入：
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