快慢指针-哑节点

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = pHead;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead.next;
        while (fast != null && fast.next != null) {
            ListNode t = fast.next;
            if (fast.val != t.val) {
                slow = fast;
                fast = t;
            } else {
                while (t!=null && fast.val == t.val) {
                    t = t.next;
                }
                slow.next = t;
                fast = t;
            }
        }
        return dummyHead.next;
    }
}

以下是一些使用哑节点的实际例子，这些例子展示了哑节点在不同链表操作中的应用：

1. 插入操作

普通插入：如果没有哑节点，向链表头部插入一个新节点需要特殊处理：

if (pHead == null) {
    pHead = new ListNode(value);
} else {
     ListNode newNode = new ListNode(value);
     newNode.next = pHead;
     pHead = newNode;
}

使用哑节点：有了哑节点，插入操作可以简化为：

ListNode newNode = new ListNode(value);
newNode.next = dummyHead.next;
dummyHead.next = newNode;

这样，无论链表是否为空，插入操作都保持一致。

2. 删除操作

普通删除：如果没有哑节点，删除头节点需要特殊处理：

if (pHead != null) {
    pHead = pHead.next;
}

使用哑节点：有了哑节点，删除操作可以简化为：

if (dummyHead.next != null) {
    ListNode toDelete = dummyHead.next;
    dummyHead.next = dummyHead.next.next;
    toDelete.next = null; // 防止内存泄漏
}

这样，无论是否需要删除头节点，删除操作都保持一致。

3. 反转链表

普通反转：没有哑节点时，反转链表需要额外处理头节点：

ListNode prev = null;
ListNode current = pHead;
while (current != null) {
    ListNode nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
}
pHead = prev;

使用哑节点：有了哑节点，反转操作可以简化为：

ListNode prev = null;
ListNode current = dummyHead.next;
while (current != null) {
    ListNode nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
}
dummyHead.next = prev;

这样，反转操作不需要关心头节点的特殊性。

4. 链表排序

归并排序：在对链表进行归并排序时，哑节点可以简化合并过程：

ListNode sortedList = dummyHead;
while (pHead != null && pHead.next != null) {
    ListNode a = pHead;
    ListNode b = pHead.next;
    pHead = pHead.next.next;
    if (a.val <= b.val) {
        a.next = b.next;
        b.next = a;
        sortedList = merge(sortedList, b);
    } else {
        b.next = a;
        a.next = b.next;
        sortedList = merge(sortedList, a);
    }
}

在这个例子中，哑节点dummyHead用于存储排序后的链表，而不需要处理头节点的特殊性。

通过这些例子，我们可以看到哑节点在链表操作中提供了一种统一和简化处理的方式，使得代码更加简洁和易于理解。