如何利用双重指针实现链表操作

双重指针（也称为哑指针或哨兵节点）在链表操作中非常有用，特别是当需要简化边界条件处理、提高代码可读性和减少错误时。以下是使用双重指针实现链表操作的一些建议：

1. 合并两个有序链表：

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

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(-1)
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    if l1:
        current.next = l1
    elif l2:
        current.next = l2

    return dummy.next

2. 删除链表中的重复元素：

def deleteDuplicates(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    dummy = ListNode(-1)
    dummy.next = head
    current = dummy
    prev = dummy

    while current.next and current.next.next:
        if current.next.val == current.next.next.val:
            while current.next and current.next.val == current.next.next.val:
                current = current.next
            prev.next = current.next
        else:
            prev = current
            current = current.next

    return dummy.next

3. 反转链表：

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

4. 找到链表的中间节点：

def middleNode(head: ListNode) -> ListNode:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

5. 删除链表的倒数第k个节点：

def removeNthFromEnd(head: ListNode, k: int) -> ListNode:
    dummy = ListNode(-1)
    dummy.next = head
    first = dummy
    second = dummy

    for _ in range(k):
        first = first.next

    while first:
        first = first.next
        second = second.next

    second.next = second.next.next

    return dummy.next

这些示例展示了如何使用双重指针简化链表操作。在实际应用中，您可能需要根据具体需求调整代码。