思想

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

实例

删除链表倒数第 N 个结点 leetcode 19

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

输入：
（1）head: ListNode，一个链表
（2）n: int，指定倒数第 n 个结点

输出：
ListNode，将倒数第 n 个结点删除，返回链表头节点。

举例：
当 head = [1,2,3,4,5], n = 2 时，删除倒数第二个节点 4，返回 [1,2,3,5]。

关键点

核心是表达倒数第 n 个节点，这里的关键点是使用两个指针，让他们的差值是 n，当后面的指针到达末尾的时候，前面的指针刚好是倒数第 n 个节点。

编码

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


def remove_nth_node_from_end_of_list(head: ListNode, n: int) -> ListNode:
    # 边界条件
    if n == 0:
        return head
    if n < 0:
        raise RuntimeError('invalid n')
    # 建立 dummy 节点，方便处理边界条件
    dummy = ListNode(next=head)
    # 双指针初始化
    slow = fast = dummy
    # 建立双指针的差值
    for _ in range(n):
        if fast is None:
            raise RuntimeError('nth node from end of list not exist')
        fast = fast.next
    # 定位倒数第 n 个节点
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
    # 删除该节点
    slow.next = slow.next.next
    return dummy.next