Python 实现经典 LeetCode 算法题:链表

链表(LikedList)是线性表(Linear List)的一种,是一种非常常见数据结构,链表通过指针将一组零散的内存块串联在一起,通过不同的串联方式形成不同类型的链表结构,最常见有单链表、双链表和循环链表。

1.基础知识要点

链表的类型

  • 单链表

    Python 实现经典 LeetCode 算法题:链表_插图

  • 双链表

    Python 实现经典 LeetCode 算法题:链表_插图1

    从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱节点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

  • 循环链表

    Python 实现经典 LeetCode 算法题:链表_插图2

  • 双向循环链表

Python 实现经典 LeetCode 算法题:链表_插图3

2.常用方法和注意事项

链表本身并不复杂,但是非常容易出错,做题时一定要注意细节,多画图多举例,下面是链表问题代码实现的常用方法以及注意事项。

  1. 关键节点指针的临时复制

    头节点、尾节点以及中间动态扫描的节点,通常会用作返回节点或链接其他节点,所以经常会使用赋值操作来复制关键节点的指针(确切而言,指针在 Python 中称为引用),或者动态调整指针所指向的节点位置,来辅助完成所需操作。这个过程相当于给节点所对应的内存地址保存了一份记录点,当再次用到该节点的时候可以随时调取。

  2. 快指针和慢指针

    快慢指针的方法是构造一种位置上的相对差异,然后利用这种位置差异来完成一些特殊操作。

  3. 虚拟头(也称哨兵节点)

    虚拟头可以免去一些边界条件的特殊处理,需注意虚拟头节点返回的是它的 next 节点而不是本身。

  4. 注意边界条件的处理

    链表题非常容易出错的地方就是容易忽略边界条件讨论处理,常需要注意的边界条件有:空节点、头节点、尾节点、长度为 1 或 2 的链表。

3.反转链表

题目(LC92.Medium)

反转从位置 mn 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ mn ≤ 链表长度。

示例:

思路:

方法一:

一个比较普通的思路是分为三部分(反转前段、反转段、反转后段),分别完成三部分再拼接,因为可能存在 m=1 的情况,返回头节点也会不同,还需要特殊讨论,这种方法略繁琐。

方法二:

加入虚拟头节点,可免去讨论 m=1 的情况,然后将整个过程看成依次把反转段后面的一个节点拿到反转段最前面去,以示例为例:

到反转段继续扫描节点,依次将指针后面的节点调整到前面(range(m, n))或可理解为调整两次(range(n-m)): 第一次,把 3 调整到反转段最前面,重新调整指向,此时为:

第二次,把 4 调整到反转段最前面,重新调整指向,此时为:

反转段代码实现部分用到了 Python 的多元赋值,这个多元赋值在反转问题经常使用,可巧妙利用多元赋值右面的值不会随着赋值操作而改变,如单链表反转可以十分简单地用多元赋值实现:

但是需要注意的是,多元赋值左边是会改变的,一定要注意赋值顺序,所以上面的多元赋值部分不能写成🙃:

代码:

4.相交链表求交点

题目(LC160.Easy)

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表

Python 实现经典 LeetCode 算法题:链表_插图4

在节点 c1 开始相交。

示例 1:

Python 实现经典 LeetCode 算法题:链表_插图5

示例 2:

Python 实现经典 LeetCode 算法题:链表_插图6

示例 3:

Python 实现经典 LeetCode 算法题:链表_插图7

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

思路:

方法一(M1):

利用 set 集合,时间复杂度 O(nlogn)(因为用了 set 集合),空间复杂度 O(n)。

遍历第一个链表,将每一个节点存入 set 集合,然后遍历第二个链表,判断当前节点是否存在与 set 集合,存在则证明该节点是相交节点,直接返回,若遍历完整个链表都没有,则返回 None,表明两个链表不相交。

方法二(M2,Best):

时间复杂度 O(n) ,空间复杂度 O(1)。

先分别遍历两个链表,获知两个链表各自的长度,往后调整较长链表的指针,使之与较短链表的起始指针对齐,然后两个链表同时往后扫描,直至二者的节点相同,证明该节点是相交节点,否则返回 None,表明两个链表不相交。

代码:

5.链表求环

题目(LC142.Medium)

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 1:

Python 实现经典 LeetCode 算法题:链表_插图8

示例 2:

Python 实现经典 LeetCode 算法题:链表_插图9

示例 3:

Python 实现经典 LeetCode 算法题:链表_插图10

进阶: 你是否可以不用额外空间解决此题?

思路:

方法一(M1):

利用 set() 集合,时间复杂度 O(n) ,空间复杂度 O(n)。

非常简单,遍历链表存入 set 集合中,第一次遇到重复的就是入环节点,不过这种方法使用了额外空间。

方法二(M2,Best):

使用快慢指针,快指针每次走两步,慢指针每次走一步,这里有些数学技巧,通过分析最后得出,从头节点 head 到入环节点和从相遇节点 meet 到入环节点的距离是一样的。所以,先找到快慢指针的相遇节点,然后同时从头节点和相遇节点遍历,直到二者的节点相同,则证明该节点是入环节点。

Python 实现经典 LeetCode 算法题:链表_插图11

6.链表划分

题目(LC86.Medium)

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

思路:

这道题的思路很简单,借助两个虚拟头节点分成两个部分,然后扫描节点分别划分到不同的部分,划分完再拼接,有些类似的题还有等于的情况,也是类似的处理方法,也就是分三段拼接。

代码:

7.链表求中间节点

题目(LC876.Easy)

给定一个带有头节点 head 的非空单链表,返回链表的中间节点。

如果有两个中间节点,则返回第二个中间节点。

示例 1:

示例 2:

提示:

  • 给定链表的节点数介于 1100 之间。

思路:

方法一:

利用数组(Python 中的列表),时间复杂度 O(N),空间复杂度 O(N);

按顺序将每个节点放入数组 A 中。然后中间节点就是 A[A.Length/2],因为我们可以通过索引检索每个节点。

方法二:

当用慢指针 slow 遍历链表时,让另一个指针 fast 的速度是它的两倍。

fast 到达链表的末尾时,slow 必然位于中间。

8.删除链表倒数第 n 个节点

题目(LC19.Medium)

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头节点。

示例:

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

思路:

利用快慢指针,定位倒数 n+1 节点位置。快指针 fast 先走 n+1 步,然后快慢指针一同遍历,当快指针 fast 到达链表末尾时,慢指针 slow 必然位于倒数 n+1 节点的位置(慢指针与快指针差 n+1 步,当快指针到达链表末尾,也就意味着慢指针与链表末尾的距离是 n+1 步),然后调整该节点指向该节点的下下一个指针(倒数 n-1 节点),完成删除导数 n 节点的操作。

另外,这里依然使用使用虚拟头,可方便删除第一个节点。

9.复杂链表的复制

题目(LC138.Medium)

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝

示例:

Python 实现经典 LeetCode 算法题:链表_插图12

提示:

  1. 你必须返回给定头的拷贝作为对克隆列表的引用。

思路:

本题的关键在于随机指针的指向,需要额外的存储空间记录随机指针的相对关系,这里主要借助字典(哈希表)来记录新旧链表各个对应节点的映射。

代码:

10.有序链表的合并

题目(LC23.Hard):

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

思路:

方法一(M1):

将所有列表的所有节点都放置在一个额外的列表中,然后对这个列表排序,为了方便返回最小的头节点,这里使用降序排序,然后将这些节点由大到小,由右及左的顺序链接到一起,最后一个节点便是最小的头节点。

时间复杂度分析:使用 sorted()函数排序,Python 的内置函数 sorted()底层实现是归并排序,时间复杂度是 O(nlogn),设有 k 个链表,每个链表有 n 个节点,因此共有 kn 个节点需要排序,所以第一种方法的时间复杂度是 O(kn*log kn)。

方法二(M2,Best):

分治法和递归法,每两个链表合并一个,然后再次两两合并,通过递归完成所有链表的合并。

时间复杂度分析:设有 k 个链表,每个链表有 n 个节点

第 1 轮:进行 k/2 次,每次处理 2n 个数字;

第 2 轮:进行 k/4 次,每次处理 4n 个数字;

……

最后一轮:进行 $k/(2^{\log k})$次,每次处理 $2^{\log k} *n$个值。

则有 $2n*k/2 + 4n*k/4+8n*k/8+\cdots+2^{\log k}*n*k/(2^{\log k})=kn+kn+kn+\cdots+kn=O(kn\log k)$,

所以第二种方法的时间复杂度是 O(kn*log k)。

代码:

© 除特别注明外,本站所有文章均为卢明冬的博客原创 , 转载请联系作者。
© 本文链接:https://lumingdong.cn/python-implements-classical-leetcode-algorithm-linked-list.html
相关文章
发布一条评论吧