思想

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

实例

合并两个升序链表 leetcode 21

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

输入：
（1）list1: ListNode，升序链表
（2）list2: ListNode，升序链表

输出： ListNode

举例：
l1 = [1,2,4], l2 = [1,3,4]
合并两个链表形成一个新的升序链表 [1,1,2,3,4,4]

用一个指针指向 l1 的 head，另一个指针指向 l2 的 head。
这两个关键节点把握着合成新的升序链表的核心，然后合成链表从 dummy 节点开始向后延伸，使用虚拟节点可以简化对于空链表等边界条件的处理。

编码

from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_two_sorted_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # 虚拟节点，方便直接返回合成链表
    dummy = ListNode()
    # 合成链表的当前指针，初始位置指向虚拟节点
    cur = dummy
    # 双指针分别指向两个升序链表的 head
    p1 = list1
    p2 = list2
    # 合成升序链表
    while p1 or p2:
        v1 = p1.val if p1 else None
        v2 = p2.val if p2 else None
        if v1 is not None and v2 is not None:
            if v1 <= v2:
                new_node = ListNode(v1)
                p1 = p1.next
            else:
                new_node = ListNode(v2)
                p2 = p2.next
        elif v1 is not None:
            new_node = ListNode(v1)
            p1 = p1.next
        elif v2 is not None:
            new_node = ListNode(v2)
            p2 = p2.next
        else:
            break
        cur.next = new_node
        cur = cur.next
    return dummy.next