行业知识

实践总结：一篇搞懂链表——单链表和双指针技巧

2026-11-09 14:27:52 来源：互联网转载

单链表

1. 什么是链表

上��就是一个单链表的结构，链表由不同的结点连接在一起组成的，结点不仅包括值，还有指向下一个结点的指针，最后一个节点指向一个None。

# 使用python定义一个节点class ListNode:def __ini__(self,val=0,next=None):self.val=valself.next=next

在大多数情况下，使用头结点（第一个结点）来表示整个链表。

例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。

就比如下面这个方法：

def print_head_value(head: Optional[ListNode]) -> None:      if head is None:          print("The list is empty.")      else:          print("The value of the head node is:", head.val)

刚开始接触链表的时候我也会纳闷，尤其是从java过来的，不知道这个方法的传参怎么传，head: Optional[ListNode]这到底是什么，是传一个结点呢，还是一个链表呢，还是直接传一list。

其实，在链表中头结点不仅表示一个结点，还表示整个链表。

可以通过以下的例子看一下，传入一个[2,4,6,4,9]的列表，是怎么生成一个链表的，其中返回head就包含了整个链表的信息。

def create_linked_list(arr: list) -> Optional[ListNode]:      if not arr:          return None            head = ListNode(arr[0])  # 创建头结点      current = head      for val in arr[1:]:  # 遍历数组剩余元素          current.next = ListNode(val)  # 为每个元素创建新结点并链接          current = current.next  # 移动到下一个结点      return head  # 返回头结点

2. 添加操作 - 单链表

可参考leetcode上的图例解释，点击标题链接就到了。

其实，举个例子就是：把一个链表理解成一列火车，把一节装满货物的车厢（结点），连接到一列火车的不同位置（index），如果连接到火车两端的话，只要把链接勾（就是链表指针）挂在别的车厢，或者被别的链接勾挂上就行，如果连接到中间，那既要被后面的车厢链接勾连接，你还要连接前面的车厢。

3.删除操作-单链表

删除就可以理解为，从一列火车上，拆除不需要的车厢下来。特殊的就是拆除车头和车尾稍微有点不同。

4.设计一个链表

每个人的设计可能不一样，我也是弄了好久才跑通所有的案例，其中遇到最多的一个问题就是，在curr.next之前，一定要判断curr是否可能为None

如果自己没思路写不出来，可以直接先拿过去看和理解，不要一直在那里耗着。

# 定义一个节点class ListNode:    def __init__(self,val=0,next=None):       self.next=next       self.val=valclass MyLinkedList:    # 初始化链表    def __init__(self):        self.head=None        self.size=0    # 获取index位置上的链表节点    def get(self, index: int) -> int:        if index=self.size:            return -1                curr=self.head        # 根据index遍历到该结点        for _ in range(index):            curr=curr.next        if curr is None:            return -1        return curr.val    # 增加值为val的头节点    def addAtHead(self, val: int) -> None:        # 实例化插入的节点        node =ListNode(val)        # 将node下一个节点指向头节点        node.next=self.head        # 将node置为头节点        self.head=node        self.size+=1    # 增加值为val的尾节点    def addAtTail(self, val: int) -> None:        node=ListNode(val)        curr=self.head        if curr is None:            self.head=node        else:            # 当curr.next不为None时,遍历到尾节点            while curr.next:                curr=curr.next            curr.next=node        self.size+=1    # 在索引index位置插入节点           def addAtIndex(self, index: int, val: int) -> None:        if indexself.size:            return        node=ListNode(val)        # 当index等于链表长度时，正好需要插入链表的尾节点，这里要直接return掉，不然self.size会多加1        if index==self.size:            self.addAtTail(val)            return        elif index==0:            node.next=self.head            self.head=node        else:            curr=self.head            # 遍历到index的前一位            for _ in range(index-1):                curr=curr.next            # 将node的下一个节点指向原本在index的节点            node.next=curr.next            # 将index的前一位节点指向node,注意上面的和下面的这两个指向不能交换位置执行            curr.next=node        self.size+=1    # 删除索引index处的节点    def deleteAtIndex(self, index: int) -> None:        if index=self.size:            return        prev=None        curr=self.head        if index==0:            self.head=curr.next        else:            # 找出index前一个节点，和index当前节点            for _ in range(index):                prev=curr                curr=curr.next            prev.next=curr.next        self.size-=1

双指针技巧

两种使用双指针技巧的情景：

两个指针从不同位置出发：一个从始端开始，另一个从末端开始；

两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

在解决环形链表的问题时，经常会用到快慢指针的方法来实现。

下面我们重点讲下，快慢指针的用法。

关于两个指针的速度应该是多少，一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

当它们相遇时，快指针所走的距离是慢指针所走距离的2倍，记住这个结论，有助于理解快慢指针。你可以理解为，相同时间内，快指针是慢指针速度的两倍，所以距离是两倍。

有了以上的概念让我们直接实战，题目详细介绍，可以点击蓝色标题，直接点击链接查看。

1. 环形链表

题目：

给你一个链表的头节点 head ，判断链表中是否有环。

解题思路：

如果是环形链表，那么快慢指针会相遇，没有相遇就说明不是环形指针

代码：

class Solution:    def hasCycle(self, head: Optional[ListNode]) -> bool:        if not head or not head.next:           return False                #尽管他们出发的节点不同，但是所用时间相同，因为是慢的走一次快的走一次，所以他们相遇时fast走得距离是慢得的两倍        slow = head        fast = head.next        while slow !=fast:            if not fast or not fast.next:                return False            slow= slow.next            fast=fast.next.next        return True

2. 环形链表II

题目：

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

解题思路：

这个可能比上一个绕一些，看了下面的代码，你可能有些疑惑，不知道为什么要先用快慢指针找到相遇点，然后换成同一速度的指针，重新走，当它们再次重合，就是链表入环的第一个结点。

这个可能需要你用笔来画一下，并且要知道一个前提，刚开始快指针是慢指针所有距离的2倍。

看下图，理解一下，你就懂了。

代码实现：

class Solution:    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:        if not head or not head.next:            return None        #尽管他们出发的节点不同，但是所用时间相同，因为是慢的走一次快的走一次，所以他们相遇时fast走得距离是慢得的两倍        slow=head        fast=head        while fast and fast.next:            slow=slow.next            fast=fast.next.next            if slow ==fast:                break        if not fast or not fast.next:            return None        slow=head        # 当两个结点相同时，就是第一个入环的结点        while slow!=fast:            slow=slow.next            fast=fast.next        return slow

3. 相交链表

题目：

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

解题思路：

先计算出两个链表的长度，找到两个链表的长度差，遍历两个链表，让长的链表的指针先走过两个链表的长度差，然后，两个链表的指针再同时走，直到相遇，即为交点。

直接看代码

class Solution:    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:        lenA=0        lenB=0        nodeA=headA        nodeB=headB        while nodeA:            lenA+=1            nodeA=nodeA.next        while nodeB:            lenB+=1            nodeB=nodeB.next                if lenA>lenB:            for _ in range(lenA-lenB):                headA=headA.next        elif lenB>lenA:            for _ in range(lenB-lenA):                headB=headB.next                while headA!=headB:            headA=headA.next            headB=headB.next        return headA

提示

在调用 next 字段之前，始终检查节点是否为空。
获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
仔细定义循环的结束条件。
运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。

4. 删除链表倒数第N个结点

题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路一：

先计算出链表的长度，然后使用长度减去n+1，得到要删除结点的前一位，通过该结点前一位指向该结点的下一位，实现删除该结点。需注意链表长度为1和链表长度相等的情况。

该方法的缺点是需要执行2次遍历遍历操作，一次是计算链表长度，一次是找到要删除结点的前一位结点。

代码实现：

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        node=head        length=0        # 计算链表的长度        while node:            length+=1            node=node.next                curr=head        if length Optional[ListNode]:        # 定义两个指针        first = head        second = head                # 将第一个指针向前移动 n+1 步        for _ in range(n + 1):            if first is None:                # 如果链表长度不足 n+1，则直接返回头结点的下一个节点                return head.next            first = first.next                    # 移动第一个和第二个指针直到第一个指针到达链表尾部        while first is not None:            first = first.next            second = second.next                # 删除倒数第 n 个节点,这里不用担心second 或 second.next为None,因为上面的for循环保证second在first之后n+1个，n+1>2        second.next = second.next.next                return head