如何利用雙重指針實現(xiàn)鏈表操作

雙重指針（也稱為啞指針或哨兵節(jié)點）在鏈表操作中非常有用，特別是當(dāng)需要簡化邊界條件處理、提高代碼可讀性和減少錯誤時。以下是使用雙重指針實現(xiàn)鏈表操作的一些建議：

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. 刪除鏈表中的重復(fù)元素：

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. 反轉(zhuǎn)鏈表：

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. 找到鏈表的中間節(jié)點：

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

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

    return slow

5. 刪除鏈表的倒數(shù)第k個節(jié)點：

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

這些示例展示了如何使用雙重指針簡化鏈表操作。在實際應(yīng)用中，您可能需要根據(jù)具體需求調(diào)整代碼。