思想

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

实例

回文链表 leetcode 234

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

输入：
head: ListNode，一个链表头结点；

输出：
bool，链表是否符合回文特征（从两端到中间经过的节点值相同）

举例：
当输入 head = [1,2,2,1] 时，从头尾到中间都是 [1,2]。

关键点

这里的关键点是从两头向中间走如何转换，因为链表是单向的，无法从尾端走向中间。
无论怎样转换，一定是要做翻转的。翻转的起始点是中间点，所以先用快慢两个指针的方式找到链表中点，fast 步长 2，slow 步长 1，当 fast 到达尾端时 slow 是中点。
然后从 slow 位置到尾端做一次翻转，接着从 head 和 slow 的位置分别遍历比较，如果有不同则不是回文。
如果想要取消翻转对原链表的影响，可以在此翻转后半部分链表。

（1）偶数 [1,2,2,1]
slow = fast = head = 1
slow = 2, fast = 2
slow = 2, fast = None
翻转变成 [1,2,1,2]
left = 1, right = 1（反转后的新头结点）
1=1, 2=2 符合回文

（2）奇数 [1,2,3]
slow = fast = head = 1
slow = 2, fast = 3 此时 fast.next = None 也应该停止。
翻转变成 [1,2,3]
left = 1, right = 3
1 != 3 不符合回文

编码

# -*- coding: utf8 -*-

from typing import Optional


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


def palindrome_linked_list(head: Optional[ListNode]) -> bool:
    # 处理边界条件
    if head is None or head.next is None:
        return True
    rtn = True
    # 获取链表中点
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    # 翻转后半部分链表
    pre, cur = None, slow
    while cur is not None:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    # 回文比较
    left, right = head, pre
    while right is not None:
        if right.val != left.val:
            rtn = False
            break
        left = left.next
        right = right.next
    # 恢复链表结构
    after_pre, after_cur = None, pre
    while after_cur is not None:
        tmp = after_cur.next
        after_cur.next = after_pre
        after_pre = after_cur
        after_cur = tmp
    return rtn

相关

双指针 0
双指针 1
双指针 2
双指针 3
双指针 4
双指针 5
双指针 6