小指针

V1

2023/03/07阅读:14主题:Pornhub黄

【打穿力扣】基础算法之链表题目基础攻略

基本概念

链表实在太重要啦,不仅仅在面试中高频出现,工作中也处处都是链表的痕迹。

在数据库中,链表被用来实现存储索引和记录等;在内存管理中,可以用链表实现动态内存分配;还可以实现其他数据结构,如:栈、队列等。

链表如此重要,相关文章也数不胜数🤣,因此,本文不会着重深入其细节,而是以题目为基础,介绍链表题目的解决方案和技巧。

虽说如此,我们还是要先简单的了解一下链表。

链表的概念

链表是最简单的线性基础数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。这些节点不需要在内存中连续地存储,因此可以动态地添加或删除节点,基于此,又衍生出许多基本链表的变种:双向链表、循环链表、静态链表等等。

链表的优势

  1. 插入和删除操作快速:链表中插入或删除节点不需要像数组一样移动其他元素,只需要改变相邻节点的指针即可。这使得链表在插入和删除大量元素时更加高效。

  2. 链表可以存储大量数据:由于链表中的节点不需要在内存中连续存储,因此链表可以存储大量数据。当需要处理大量数据时,链表的优势更加明显。

  3. 链表支持动态分配内存:链表中的节点可以动态分配内存,因此可以根据实际需要添加或删除节点。这使得链表在需要频繁添加或删除元素时更加方便。

链表的基础实现

说白了,链表就是以指针串联起来的多个节点,因此,一个基础单链表必备的是节点存储的值,以及节点上的指针。

以下代码以pythonC++语言为示例,定义一个单链表节点,其他语言同理。

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的指针,然后我们把最后一个节点当做头结点,即可完成反转。

为了完成这一任务,我们可以使用双指针,具体操作如下:

  1. 设置一个指针为cur指向当前的节点;一个指针为pre指向当前节点的上一个节点,如此,我们只需要执行cur.next = pre,就可以完成新建指针;

  2. 然后向后移动两个指针,把pre移动到cur的位置,cur移动到原cur.next的位置;

  3. 注意一个关键点,在操作1中,我们把cur.next指向了pre,因此丢失了原cur.next,所以我们要在执行操作1之前,先用一个临时变量存储一下原cur.next

  4. 注意另一个关键点,当链表反转之后,原头结点需要指向空,因此,初始化的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

环形链表

给出一个链表,请你检测链表是否有环,如果有环,请返回入环节点。

题目分析

环形链表有一个经典的做法,叫做“快慢指针” ,顾名思义,在这个做法中,有两个指针,快指针一次走两步,慢指针一次走一步,如果两个指针相遇说明链表中存在环;如果快指针走到了空节点,说明链表中没有环

进一步的,当两个指针相遇之后,如果将慢指针指向头结点,然后两个指针都是每次都一步,当他们在相遇的时候就是环的入口节点。

(快慢指针的正确性证明,可以参考这篇文章,本文主要是讲解实现。)

快慢指针的实现,具体操作如下:

  1. 初始化快慢指针指向头结点;

  2. 快指针走两步,慢指针走一步,以快指针当前节点及其下一个节点,是否存在为循环条件;

  3. 当两个指针相遇时,重置快指针到头结点。然后两个指针,每次走一步(快指针也走一步),直到他们再次相遇,相遇点即是环的入口;

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是第一个节点的话,它的前面没有节点,因此不好完成删除操作,此时就需要用到虚拟节点,我们创建一个虚拟节点,让它指向第一个节点,这样当第一个节点是目标节点的时候,我们就可以用前面提到的方法删除它。

具体操作如下:

  1. 创建一个虚拟节点dummy,让它指向头结点head

  2. 初始化两个指针p1p2,一个指向dummy,一个指向head;

  3. 使用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

相交链表

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

图示两个链表在节点 c1 开始相交:

题目分析

我们可以把整个链表看做三部分:链表A,链表B,A和B共同的部分链表C。我们从A和B开始同步遍历,假如遍历到了空节点,就把指针指向另一个链表的头部,最后,如果走到了相同的节点,则说明链表相交,否则说明不相交。

具体操作如下:

  1. 初始化,两个指针p1和p2,其中p1指向a1,p2指向b1

  2. 以 两个指针 指向的节点 是否相同 为循环条件。两个指针,同步向后移动,若指针p1走到了末尾则让p1指向b1;若指针p2走到了末尾,则让p2指向a1;

  3. 最后,如果链表相交,则两个指针指向的节点就是相交链表的第一个节点,否则两个指针指向的节点都是空;

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步到了链表末尾,假如没有虚拟节点,那么后走指针初始化指向头结点,则无法完成删除头结点。

具体的做法:

  1. 初始化虚拟节点,并指向头结点,初始化两个指针,先走指针p1指向头结点、后走指针p2指向虚拟节点;

  2. 先走指针p1走n步;

  3. 后走指针p2与先走指针p1同时走,直到 先走指针p1 到链表末尾;

  4. 使用p2执行删除操作;

  5. 我们最后返回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 ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。

题目分析

本题是比较直观的模拟题目,我们要把奇数索引的节点串在一起,偶数索引的节点串在一起,然后把奇数链的尾部指向偶数链的头部即可,所以没有思维上的难度,重点在于代码实现上。

具体的操作:

  1. 设定两个指针p1和p2,其中p1指针用来连接奇数节点,p2指针用来连接偶数节点;

  2. p1指向下一个奇数节点,并前进两步;p2指向下一个偶数节点,并前进两步;

  3. p1指针指向p2的头结点;

  4. 有一个需要注意的关键点,为了完成第三步,我们需要额外创建一个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

删除链表中重复的元素

给出一个已经排序的链表,如果链表中的元素存在重复,则将所有重复的数字全删掉。

题目分析

本题要求把所有重复的数字全部删掉,那我们很容易就能想到,可以使用双指针,一个指针负责遍历所有重复的元素,一个指针负责删除

有一个关键的地方,如果给出的头结点就是我们要删除节点,那么就需要额外去处理头结点,所以我们需要使用虚拟结点

具体的:

  1. 创建一个虚拟节点,让其指向头结点,初始化两个指针p1和p2;

  2. 向后移动p2,如果p2的当前元素和下一个元素相同,则一直向后,如此,p2的下一个元素则一定是不同元素。

  3. 假如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道题,总结出一些解决链表题目需要注意的常见事项:

  1. 调用next之前,必须检查指针是否为空,例如:我们想调用p1.next,就要判断p1不为空;我们想调用p1.next.next,就要判断p1p1.next都不为空;

  2. 必须注意,当前的指针 初始化后所指向的结点 是否在指针移动之后 仍需要使用,如果仍需要使用,那我们应该再创建一个其他指针,用来遍历,比如:在【奇偶链表】这题中,我们定义了偶数链表的头结点p2_head = head.next之后,因为后续仍然需要使用p2_head,所以不可以直接用它去遍历,而是要另外创建一个指针p2 = p2_head

  3. 当给出的头结点有可能是需要处理的节点之一时,最好在前面接一个虚拟节点,这样可以不去特殊处理头结点,比如:在删除节点的时候中,我们使用了双指针删除,那么如果要删除的节点可能是头结点,就需要额外判断。

  4. 在大多数可以用双指针解决的单链表题目中,优先考虑使用一个指针向前遍历,另一个指针一直跟在它的后面,也就是跟踪当前节点和当前节点的前一个节点。

  5. 链表问题的时空复杂度不好分析,假如只使用了指针,那么空间复杂度是O(1)的;而时间复杂度通常取决于遍历链表的次数,因为访问链表中的任何一个节点都需要遍历整个链表。

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1