【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解

 🎉🎉欢迎光临🎉🎉

🏅我是苏泽，一位对技术充满热情的探索者和分享者。🚀🚀

🌟特别推荐给大家我的最新专栏《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. 首先，我们遍历原始链表，对于每个节点，创建一个新节点，并将其插入到原节点的后面。这样我们就可以同时访问原始节点和新节点。例如，原始链表为 1 -> 2 -> 3，复制后变为 1 -> 1' -> 2 -> 2' -> 3 -> 3'。

   原始链表：   1 -> 2 -> 3
   复制后的链表： 1' -> 2' -> 3'

2. 然后，我们再次遍历链表，这次是为了设置每个新节点的随机指针。我们根据原节点的随机指针找到对应的新节点，并将其设置为新节点的随机指针。例如，如果原节点 2 的随机指针指向 3，那么新节点 2' 的随机指针应该指向 3'。

   原始链表：   1 -> 2 -> 3
   复制后的链表： 1' -> 2' -> 3'
   随机指针：    N -> 2 -> N
   复制后的随机指针： N -> 2' -> N

3. 最后，我们将新旧节点分离，并返回复制链表的头节点。例如，将 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 = valself.next = nextself.random = randomdef cloneRandomNode(head):if not head:return None# 第一步：复制每个节点，并将新节点插入原节点后面curr = headwhile curr:new_node = Node(curr.val)new_node.next = curr.nextcurr.next = new_nodecurr = new_node.next# 第二步：设置每个新节点的随机指针curr = headwhile curr:curr.next.random = curr.random.next if curr.random else Nonecurr = curr.next.next# 第三步：分离新旧节点，返回复制链表的头节点curr = headnew_head = head.nextwhile curr:next_old = curr.nextnext_new = curr.next.nextcurr.next = next_newif next_new:curr.next.next = next_oldcurr = next_oldreturn 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. 我们使用最小堆来存储每个链表的头部节点。这样可以快速地找到当前最小的节点。例如，如果有三个链表分别为 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)
   

2. 我们创建一个虚拟头节点 dummy，用于连接所有合并后的节点。

3. 我们不断从最小堆中取出最小的节点，将其连接到结果链表中，并将该节点的下一个节点加入堆中，直到堆为空。例如，我们从最小堆中取出 (1, node1)，将其连接到结果链表中，然后将 node1.next（即值为 4 的节点）加入堆中。

   结果链表：     dummy -> 1
   最小堆：      (1, node2), (4, node4), (6, node6)
   

4. 最后，我们返回合并后链表的头节点。例如，最终的结果链表为 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, Optionalclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef 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.nextif node.next:heapq.heappush(min_heap, (node.next.val, node.next))return dummy.next