花溪区生态文明建设局网站,重庆天蚕网络科技有限公司,有名的网站,电影网站怎么做的#x1f389;#x1f389;欢迎光临#x1f389;#x1f389; #x1f3c5;我是苏泽#xff0c;一位对技术充满热情的探索者和分享者。#x1f680;#x1f680; #x1f31f;特别推荐给大家我的最新专栏《Spring 狂野之旅#xff1a;底层原理高级进阶》 #x1f680… 欢迎光临 我是苏泽一位对技术充满热情的探索者和分享者。 特别推荐给大家我的最新专栏《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, val0, nextNone, randomNone):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 - 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, Optionalclass ListNode:def __init__(self, val0, nextNone):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
