小指针
2023/03/07阅读:14主题:Pornhub黄
【打穿力扣】基础算法之链表题目基础攻略
基本概念
链表实在太重要啦,不仅仅在面试中高频出现,工作中也处处都是链表的痕迹。
在数据库中,链表被用来实现存储索引和记录等;在内存管理中,可以用链表实现动态内存分配;还可以实现其他数据结构,如:栈、队列等。
链表如此重要,相关文章也数不胜数🤣,因此,本文不会着重深入其细节,而是以题目为基础,介绍链表题目的解决方案和技巧。
虽说如此,我们还是要先简单的了解一下链表。
链表的概念
链表是最简单的线性基础数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。这些节点不需要在内存中连续地存储,因此可以动态地添加或删除节点,基于此,又衍生出许多基本链表的变种:双向链表、循环链表、静态链表等等。
链表的优势
-
插入和删除操作快速:链表中插入或删除节点不需要像数组一样移动其他元素,只需要改变相邻节点的指针即可。这使得链表在插入和删除大量元素时更加高效。
-
链表可以存储大量数据:由于链表中的节点不需要在内存中连续存储,因此链表可以存储大量数据。当需要处理大量数据时,链表的优势更加明显。
-
链表支持动态分配内存:链表中的节点可以动态分配内存,因此可以根据实际需要添加或删除节点。这使得链表在需要频繁添加或删除元素时更加方便。
链表的基础实现
说白了,链表就是以指针串联起来的多个节点,因此,一个基础单链表必备的是节点存储的值,以及节点上的指针。
以下代码以python
和C++
语言为示例,定义一个单链表节点,其他语言同理。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
遍历单链表
遍历链表是几乎所有链表题目的基础,要想遍历整个链表,访问链表中的所有节点,我们可以这样做:
p = head # 初始化指针p 指向 头结点
while p:
# p指向链表中的当前节点
print(p.val)
p = p.next
需要注意的是,为了保证不改变头结点head
的引用,我们必须让另一个指针p
指向head
,然后使用指针p
来遍历整个链表,这点非常重要,需要谨记,在任何对链表本身进行遍历的时候,都需要额外使用一个指针,保证我们总是能通过head
获取到完整的原本的链表。
高频链表题目解法
❝解决链表题目,画图是最高效的办法。
❝本文主要以单链表为基准,因为大部分链表题是以单链表为主,假如同样的单链表问题变成双链表,会使题目难度骤减。
双指针+虚拟节点
链表是使用指针进行连接的,因此,对于链表的操作离不开对于指针的运用,而双指针又是解决链表问题中的常用手段,许多经典链表问题都需要双指针完成,例如:反转链表、环形链表,移出链表元素等。
而虚拟节点一般是为了避免对于头结点进行特殊处理,而增加的一个特殊的“哨兵”节点。下面我们通过几个经典的题目,来讲解该组合在解决问题中的用法。
反转链表
❝反转一个单链表。如下图所示:
![]()
题目分析
想要使链表反转过来,一个直观的思路是:将A指向B的指针,变成B指向A,就可以将整个链表反转。
考虑,如何实现我们的这个思路呢?
可以画图来解决,基于链表是使用指针确定下一个节点是谁的这一事实,我们可以直接创建出由B指向A的指针,而不必去管A指向B的指针,然后我们把最后一个节点当做头结点,即可完成反转。

为了完成这一任务,我们可以使用双指针,具体操作如下:
-
设置一个指针为
cur
指向当前的节点;一个指针为pre
指向当前节点的上一个节点,如此,我们只需要执行cur.next = pre
,就可以完成新建指针; -
然后向后移动两个指针,把
pre
移动到cur
的位置,cur
移动到原cur.next
的位置; -
注意一个关键点,在操作1中,我们把
cur.next
指向了pre
,因此丢失了原cur.next
,所以我们要在执行操作1之前,先用一个临时变量存储一下原cur.next
; -
注意另一个关键点,当链表反转之后,原头结点需要指向空,因此,初始化的
cur
为头结点head
,而pre
应该为None
;
Code
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre, cur = cur, tmp
return pre
环形链表
❝给出一个链表,请你检测链表是否有环,如果有环,请返回入环节点。
![]()
题目分析
环形链表有一个经典的做法,叫做“快慢指针” ,顾名思义,在这个做法中,有两个指针,快指针一次走两步,慢指针一次走一步,如果两个指针相遇说明链表中存在环;如果快指针走到了空节点,说明链表中没有环。
进一步的,当两个指针相遇之后,如果将慢指针指向头结点,然后两个指针都是每次都一步,当他们在相遇的时候就是环的入口节点。
(快慢指针的正确性证明,可以参考这篇文章,本文主要是讲解实现。)
快慢指针的实现,具体操作如下:

-
初始化快慢指针指向头结点;
-
快指针走两步,慢指针走一步,以快指针当前节点及其下一个节点,是否存在为循环条件;
-
当两个指针相遇时,重置快指针到头结点。然后两个指针,每次走一步(快指针也走一步),直到他们再次相遇,相遇点即是环的入口;
Code
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
fast = head
while slow != fast:
slow = slow.next
fast = fast.next
return fast
return None
移出链表中的元素
❝给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。![]()
题目分析
假如本题是数组,那么这个问题非常简单,我们只需要用一个指针遍历数组,遇到等于val
的元素,直接删掉即可。
但是假如是链表的话,用一个指针遍历,当我们遇到目标节点的时候,需要用前一个指针来完成删除操作,但是此时已经失去了前一个指针,所以本题我们仍然需要两个指针,一个指针遍历链表找到目标元素,另一个指针完成删除操作。

使用这种做法,假如val
是第一个节点的话,它的前面没有节点,因此不好完成删除操作,此时就需要用到虚拟节点,我们创建一个虚拟节点,让它指向第一个节点,这样当第一个节点是目标节点的时候,我们就可以用前面提到的方法删除它。
具体操作如下:
-
创建一个虚拟节点
dummy
,让它指向头结点head
; -
初始化两个指针
p1
和p2
,一个指向dummy
,一个指向head
; -
使用
p2
遍历链表,当遇到目标节点的时候,用p1
删除目标节点,当前节点如果不是目标节点,则让p1
指向p2
的位置;
Code
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(-1)
dummy.next = head
p1, p2 = dummy, head
while p2:
if p2.val == val:
p1.next = p2.next
else:
p1 = p2
p2 = p2.next
return dummy.next
相交链表
❝给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。图示两个链表在节点
c1
开始相交:![]()
题目分析
我们可以把整个链表看做三部分:链表A,链表B,A和B共同的部分链表C。我们从A和B开始同步遍历,假如遍历到了空节点,就把指针指向另一个链表的头部,最后,如果走到了相同的节点,则说明链表相交,否则说明不相交。
具体操作如下:

-
初始化,两个指针p1和p2,其中p1指向a1,p2指向b1;
-
以 两个指针 指向的节点 是否相同 为循环条件。两个指针,同步向后移动,若指针p1走到了末尾则让p1指向b1;若指针p2走到了末尾,则让p2指向a1;
-
最后,如果链表相交,则两个指针指向的节点就是相交链表的第一个节点,否则两个指针指向的节点都是空;
Code
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p1, p2 = headA, headB
while p1 != p2:
p1 = p1.next if p1 else headB
p2 = p2.next if p2 else headA
return p1
删除链表的倒数第N个节点
❝给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例:删除倒数第二个节点。
![]()
题目分析
本题需要删除倒数第n个节点,但是只给出了头结点,直观的思路是:先遍历一遍链表,获得链表的总长度,然后用总长度减去n得出长度,然后遍历到这个长度,再执行删除。
这样子做需要两次遍历,但是如果使用双指针,我们就可以在一次遍历中,完成删除操作。
我们先初始化两个指针,一个指针先走n步之后,两个指针一起移动,这样两个指针之间差了n步,当先走指针到达链表末尾的时候,后走指针正好指向了倒数第n个元素的前一个元素,顺利执行删除操作。
还有一个点需要注意,我们需要设置一个虚拟节点指向头结点,这样当要删除的节点指向头结点的时候,我们不需要特殊处理。
当给出的n与链表长度相等的时候,倒数第n个节点就是头结点,此时,先走指针走n步到了链表末尾,假如没有虚拟节点,那么后走指针初始化指向头结点,则无法完成删除头结点。
具体的做法:

-
初始化虚拟节点,并指向头结点,初始化两个指针,先走指针p1指向头结点、后走指针p2指向虚拟节点;
-
先走指针p1走n步;
-
后走指针p2与先走指针p1同时走,直到 先走指针p1 到链表末尾;
-
使用p2执行删除操作;
-
我们最后返回
dummy.next
,也就是head
也就是原链表的头结点;
Code
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(-1, head)
p1, p2 = head, dummy
while n:
p1 = p1.next
n -= 1
while p1:
p1 = p1.next
p2 = p2.next
p2.next = p2.next.next
return dummy.next
奇偶链表
❝给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
![]()
题目分析
本题是比较直观的模拟题目,我们要把奇数索引的节点串在一起,偶数索引的节点串在一起,然后把奇数链的尾部指向偶数链的头部即可,所以没有思维上的难度,重点在于代码实现上。
具体的操作:

-
设定两个指针p1和p2,其中p1指针用来连接奇数节点,p2指针用来连接偶数节点;
-
p1指向下一个奇数节点,并前进两步;p2指向下一个偶数节点,并前进两步;
-
p1指针指向p2的头结点;
-
有一个需要注意的关键点,为了完成第三步,我们需要额外创建一个p2指针用来遍历偶数链表,以保证在合并的时候,不丢失偶数链表的头节点。
Code
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return None
t = head.next # p2_head
p1, p2 = head, t
while p2 and p2.next:
p1.next = p2.next
p1 = p2.next
p2.next = p1.next
p2 = p1.next
p1.next = t
return head
删除链表中重复的元素
❝给出一个已经排序的链表,如果链表中的元素存在重复,则将所有重复的数字全删掉。
![]()
题目分析
本题要求把所有重复的数字全部删掉,那我们很容易就能想到,可以使用双指针,一个指针负责遍历所有重复的元素,一个指针负责删除。
有一个关键的地方,如果给出的头结点就是我们要删除节点,那么就需要额外去处理头结点,所以我们需要使用虚拟结点。
具体的:

-
创建一个虚拟节点,让其指向头结点,初始化两个指针p1和p2;
-
向后移动p2,如果p2的当前元素和下一个元素相同,则一直向后,如此,p2的下一个元素则一定是不同元素。
-
假如p2被移动过,说明有相同元素,我们把所有的相同元素都删除,否则向后移动p1;
Code
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1, head)
p1, p2 = dummy, head
while p2:
t = p2 # 用t来判断p2是否移动过
while p2.next and p2.val == p2.next.val:
p2 = p2.next
if t != p2: # 移动过说明有相同元素 则删除
p1.next = p2.next
else:
p1 = p1.next
p2 = p2.next
return dummy.next
总结
上面,我列举出了7道超级高频的链表题目,无一例外,它们都可以使用双指针+虚拟节点的技巧来解决,那么根据这7道题,总结出一些解决链表题目需要注意的常见事项:
-
调用next之前,必须检查指针是否为空,例如:我们想调用
p1.next
,就要判断p1
不为空;我们想调用p1.next.next
,就要判断p1
和p1.next
都不为空; -
必须注意,当前的指针 初始化后所指向的结点 是否在指针移动之后 仍需要使用,如果仍需要使用,那我们应该再创建一个其他指针,用来遍历,比如:在【奇偶链表】这题中,我们定义了偶数链表的头结点
p2_head = head.next
之后,因为后续仍然需要使用p2_head
,所以不可以直接用它去遍历,而是要另外创建一个指针p2 = p2_head
。 -
当给出的头结点有可能是需要处理的节点之一时,最好在前面接一个虚拟节点,这样可以不去特殊处理头结点,比如:在删除节点的时候中,我们使用了双指针删除,那么如果要删除的节点可能是头结点,就需要额外判断。
-
在大多数可以用双指针解决的单链表题目中,优先考虑使用一个指针向前遍历,另一个指针一直跟在它的后面,也就是跟踪当前节点和当前节点的前一个节点。
-
链表问题的时空复杂度不好分析,假如只使用了指针,那么空间复杂度是O(1)的;而时间复杂度通常取决于遍历链表的次数,因为访问链表中的任何一个节点都需要遍历整个链表。
END
作者介绍