基本概念

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

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

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

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

链表的概念

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

链表的优势

插入和删除操作快速：链表中插入或删除节点不需要像数组一样移动其他元素，只需要改变相邻节点的指针即可。这使得链表在插入和删除大量元素时更加高效。
链表可以存储大量数据：由于链表中的节点不需要在内存中连续存储，因此链表可以存储大量数据。当需要处理大量数据时，链表的优势更加明显。
链表支持动态分配内存：链表中的节点可以动态分配内存，因此可以根据实际需要添加或删除节点。这使得链表在需要频繁添加或删除元素时更加方便。

链表的基础实现

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

以下代码以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