理论篇
链表是线性表的链式存储,它不需要使用地址连续的存储单元,而是通过指针建立数据元素之间的逻辑关系。
- 优点:插入、删除操作不需要移动元素,只需要修改指针;
- 缺点:不支持随机存取,不能直接找到表中某个特定的节点,需要从头开始遍历,依次查找;
类别 | 顺序表 | 链表 |
---|---|---|
存取方式 | 顺序存取、随机存取 | 不支持随机存取 |
存储结构 | 逻辑相邻位置也相邻 | 逻辑相邻位置不一定相邻 |
查找 | 按序查找O(1) | 按序查找O(n) |
插入、删除 | 需要移动众多元素 | 只需修改指针O(1) |
空间分配 | 预先分配足够大的空间 | 需要时分配 |
单链表
单链表:即线性表的链式存储,通过一组任意的存储单元来存储链表节点,每个节点包含数据域和后继指针域。
单链表的存储结构
python实现:
1 | class ListNode(object): |
头结点:在单链表第一个节点之前附加一个节点,称为头结点,头结点值域可以不设任何信息,也可记录表长等信息。头指针能够统一第一个位置和其他位置上的很多操作(特别是插入、删除),使得代码逻辑更加清晰。
单链表的基本操作
创建
可通过头插法和尾插法两种方式创建单链表:
- 头插法:每次将新节点插入到第一个位置,链表节点顺序和原始输入顺序逆序
1 | def create_link(nums): |
- 尾插法:每次将新节点插入到链表尾部,与输入顺序相同
1 | def create_link(nums): |
查找
- 按值查找:从前向后依次比较,找到则返回
1 | def get_element_by_val(head,val): |
- 按序号查找:查找第i个节点,链表计数时,注意初始对齐,即初始count的值对应初始节点,条件不满足时的coun的值对应最终节点;
1 | def get_element_by_id(head,i): |
遍历
- 获取链表长度:遍历的同时统计计数
1
2
3
4
5
6
7
8
9
10def get_length(head):
"""
获取链表head的长度
"""
p = head
count = 0
while p:
p = p.next
count += 1
return count - 获取尾指针:根据尾指针的next域为None来查找
1 | def get_tail(head): |
插入
- 在第i-1个节点之后插入:要插入节点,需要找到其对应的前驱节点
1 | def insert_node(head,i,val): |
- 在第i个节点之前插入:如果无法获取其前驱节点,可通过换值实现插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20def insert_node(head,i,val):
"""
在第i个节点之前插入新节点
"""
p = dummy = ListNode(0)
dummy.next = head
if i < 1:
return False
count = 0
while p and count < i:
p = p.next
count += 1
if not p:
return Fasle
else:
new_node = ListNode(val)
# 插入第i个节点之后,再换值
p.next,new_node.next = new_node,p.next
p.val,new_node.val = new_node.val,p.val
return dummy.next
删除
删除第i-1个节点的后继节点:同样的要删除一个节点需要先找到其对应的前驱节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14def del_node(head,i):
p = dummy = ListNode(0)
dummy.next = head
if i < 1:
return False
count = 0
while p and count < i-1:
p = p.next
count += 1
if p is None or p.next is None:
return Fasle
else:
p.next = p.next.next
return dummy.next删除第i个节点:如果无法找到前驱节点,可删除第i个节点的后继节点,然后再将第i个节点中的值替换为其后继节点中的值
1 | def del_node(head,i): |
双链表
单链表无法直接获取前驱节点,需要从头重新遍历,时间复杂度为O(n),双链表通过引入前驱指针解决了这个问题。
双链表的存储结构
python实现:
1 | class Doublelink(object): |
双链表的基本操作
双链表的查找和单链表基本一致,只不过多了一个反向查找的方向;双链表的插入和删除操作前后需要保持双链表的基本结构,加入需要在p节点后插入一个新节点node:
1 | p.next.prior, node.next, p.next, node.prior = node,p.next.next, node, p |
循环单链表
- 循环单链表在单链表的基础上使得尾节点的next指针指向头结点,构成一个环;这样做的好处是可以在任意位置遍历整个链表。
- 如果对单链表常做的操作是在表头和表尾,此时可使用带尾指针的循环链表;
循环双链表
- 循环双链表是在双链表的基础上使得尾节点的next指向头结点,使头节点的prior指向尾节点;
实战篇
链表中常用技巧
- 绘图:链表操作常常涉及到很复杂的指针变换,建议先画出操作图示,按图示理清算法思路后再进行代码编写;
- 序列赋值:python的序列赋值给多个指针赋值带来了巨大便利,牢记序列赋值的两个关键点:
- 右侧生成元组:右侧多个对象会生成一个临时元组,指向这些变量所对应的原始对象,只要这些对象在赋值期间没有被原地修改,就能保持原始的值;
- 左侧依序赋值:依次将元组中的对象按左侧变量的顺序进行赋值;如果前面的赋值会改变后面的变量含义,则应将后面的变量放在前面先进行赋值;
- 头结点:引入头结点能够统一所有位置上的操作,简化代码逻辑;
- 分身哨兵:在移动指针时,如果后续还需要用到该位置的指针,可以复制一个分身哨兵代替原来的指针进行移动;
- 递归:链表的递归式结构决定了很多问题都可以通过递归的思路来求解;
- 快慢指针:通过快慢指针可以找到链表的(上/下)中位数、还可以判断链表是否有环、以及环的入口;
- 分类重组:如果需要将链表按照某种条件进行重排,可以将满足条件的单独作为一个链表,不满足条件的单独作为一个链表,最后再将它们拼接;
LeetCode经典题目
反转链表
- 问题:反转单链表
- 思路:三指针法,pre代表新链表头指针,head代表旧链表头指针,head.next代表旧链表头指针的下一个节点;head加入到pre,head移动到head.next,pre移动到head。
- 代码:核心
head.next,pre,head = pre,head,head.next
1 | def reverseList(self, head): |
反转链表II
- 问题:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转
- 思路:找到m-1位置的节点作为pre_start,第m位置的节点start,第n位置节点end,第n+1位置节点end_next,对m-n范围内的链表进行逆转,再和其他段拼接
- 代码:
1 | class Solution(object): |
合并两个有序链表
- 问题:将两个有序链表合并为一个新的有序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的;
- 思路:创建一个个新的头节点,比较两个链表的节点,依次将较小者插入到新链表尾部,直至某个链表为空,再将另一个链表连接至新链表末尾;
- 代码:核心
p.next = l1 or l2
1 | def mergeTwoLists(self, l1, l2): |
合并K个有序链表
- 问题:合并 k 个排序链表,返回合并后的排序链表
- 思路:使用二路归并排序算法
- (1)先将k个链表划分为两组,递归地对这两组链表进行合并,如果某组链表只有一条就直接返回这条链表;
- (2)然后对合并后的两条有序链表进行合并;
- 代码:核心是分组、合并2条有序链表
1 | def mergeKLists(self, lists): |
回文链表
- 问题:判断一个链表是否为回文链表
- 思路:找到中位数(下中位数)-前半部分逆序-对比前后部分,全相同才是回文链表
- 代码:核心是寻找中位数
1 | def isPalindrome(self, head): |
相交链表
- 问题:找到两个单链表相交的起始节点
- 思路:跑完自己跑对方,首遇非空即为交点,为空则无交点
- 代码:
1 | def getIntersectionNode(self, headA, headB): |
环形链表
- 问题:给定一个链表,判断链表中是否有环
- 思路:快慢指针,快完之前相遇则有环,否则无环
- 代码:
1 | def hasCycle(self, head): |
环形链表II
- 问题:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
- 思路:快慢指针-判断环,相遇说明有环,相遇后派一个新的慢指针从头开始移动,与原始慢指针的下次相遇点既是环的入口。证明,y = (n-m)c+x,其中x是第一次相遇点到入口的距离,y是起点到入口的距离。
- 代码:
1 | def detectCycle(self, head): |
奇偶链表
- 问题:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
- 思路:分类重组,使用两个哑结点,一个向后插入奇数结点,一个向后插入偶数结点,最后再将二者合并
- 代码:
1 | def oddEvenList(self, head): |
两两交换链表中的节点
- 问题:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表,给定 1->2->3->4, 你应该返回 2->1->4->3
- 思路:交换前两个,递归求出后面的,再连接
- 代码:
1 | def swapPairs(self, head): |
k 个一组翻转链表
- 问题:给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。给定这个链表:1->2->3->4->5,当 k = 3 时,应当返回: 3->2->1->4->5。
- 思路:先统计链表长度n,总共有n/k份长度为k的需要逆序,循环逆序即可
- 代码:
1 | def reverseKGroup(self, head, k): |
排序链表
- 问题:对链表进行排序
- 思路:可以用插入排序、快排或归并排序
- 插入排序:使用两个指针,p.next代表当前待插入的元素,q.next代表已排序的节点,每次q.next从头开始遍历,直至找到第一个不小于p.next.val的节点,将其插入;
- 快排:分类重组,将节点划分为小于less、等于eq、大于more某个值的三个链表->递归地快排less和more->合并三个链表;
- 归并排序:寻找中位数-两侧归并排序(空或单节点直接返回)-合并两侧归并结果;
- 代码:
1 | # 插入排序 |
两数相加
- 问题:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
- 思路:递归思路更简洁
- 两个都有,随便用哪个节点放结果(l1,l2,flag),然后next指向子问题的解
- 其中一个没有,只需要计算有的和flag的和,next指向子问题的解
- 两个都没有且flag不为0,新建节点存储,否则返回None
- 两个都有,随便用哪个节点放结果(l1,l2,flag),然后next指向子问题的解
- 代码:
1 | def addTwoNumbers(self, l1, l2): |
两数相加II
- 问题:给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
- 思路:先逆序,再相加,转化为问题2,结果再逆序
- 代码:
1 | def addTwoNumbers(self, l1, l2): |
旋转链表
- 问题:给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数
- 思路:等价于右移k%n,这相当于将最后k%n个节点插入到头结点后面,只需要找到第n-k%n个节点和尾节点(头结点-按序查找-插入)
- 代码:
1 | def rotateRight(self, head, k): |
删除链表的倒数第N个节点
- 问题:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2。当删除了倒数第二个节点后,链表变为 1->2->3->5。
- 思路:先用一个指针p移动到第n+1个节点,然后安排另一个指针q从头节点开始移动,直至p==None,q指向了要删除节点的前一个节点。
- 代码:
1 | def removeNthFromEnd(self, head, n): |
复制带随机指针的链表
- 问题:给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。
- 思路:第一次遍历,先创建所有节点;第二次遍历,再建立节点间的连接;
- 代码:
1 | def copyRandomList(self, head): |
有序链表转换二叉搜索树
- 问题:
- 思路:中位数做根,递归地左链表作为左子树,右链表作为右子树
重排链表
- 问题:给定一个单链表 L:L0→L1→…→Ln-1→Ln ,将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
- 思路:找到中间位置的节点,将后半部分逆序,然后归并到前半部分
Split Linked List in Parts
- 问题:Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.Input: root = [1, 2, 3], k = 5,Output: [[1],[2],[3],[],[]]
- 思路:先得到每个链表的长度x,y = divmod(n,k) 分为k个链表,其中前y个长度为x+1,后面的长度为x;
Linked List Components
- 问题:给定一个链表head和列表G,返回head中有多少个连续的块,块中节点的值在G中;Input: head: 0->1->2->3 G = [0, 1, 3] Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components - 思路:在有哑元时只需要统计上一个节点不在G中当前节点在G中的个数;
删除排序链表中的重复元素 II
- 问题:给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。输入: 1->2->3->3->4->4->5 输出: 1->2->5
- 思路:pre代表可能重复的前一个节点,cur代表可能重复的第一个节点,pro代表与cur不同的第一个节点,统计pro和cur的距离,如果大于1则pre.next直接指向pro,cur移动至pro,重复统计,反之等于1,则pre,cur前进一步,直至cur为None