思想

双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。

实例

链表的中间结点 leetcode 876

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

输入：
head: ListNode，一个链表

输出：
ListNode，返回链表的中间节点。

举例：
当 head = [1,2,3,4,5] 时，返回中间节点 3，后面的链表中要有 4 和 5 两个节点。

关键点

核心是表达中间节点，这里的关键点是使用两个指针，快的一次走 2 个节点，慢的一次走 1 个节点，这样当快的到达尾端的时候，慢的到达链表的中点。
解题时要注意奇偶的边界条件：
（1）奇数
head = [1,2,3]
初始，slow = fast = dummy；
第 1 步，fast = 2，slow = 1；
第 2 步，fast = None，slow = 2；
（2）偶数
head = [1,2]
初始，slow = fast = dummy；
第 1 步，fast = 2，slow = 1；
第 2 步，fast = None，slow = 2；
（3）边界
head = [1]
初始，slow = fast = dummy；
第 1 步，fast = None，slow = 1；

编码

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def middle_of_the_linked_list(head: Optional[ListNode]) -> Optional[ListNode]:
    # 准备双指针
    dummy = ListNode(next=head)
    slow = fast = dummy
    # 按照 2 和 1 的步速遍历
    while fast is not None:
        slow = slow.next
        # fast 一般走 2 步，如果第一步到达末尾则走 1 步
        fast = fast.next if fast.next is None else fast.next.next
    return slow

相关

双指针 0
双指针 1
双指针 2
双指针 3