public class deleteDuplicates_82 {
    
    // ================= 方法 1：双指针法 =================
    public ListNode deleteDuplicates(ListNode head) {
        // 边界情况判断：如果链表为空，直接返回
        if (head == null) {
            return head;
        }
        
        // slow：慢指针，用于指向当前待比较的节点
        ListNode slow = head;
        // fast：快指针，用于探测 slow 后面的节点
        ListNode fast = head.next;
        
        // result：虚拟头节点，用于存储最终保留下来的不重复节点结果链
        ListNode result = new ListNode(0);
        // copy：结果链表的尾指针，用于串联保留的节点
        ListNode copy = result;
        
        // 当慢指针和快指针都不为空时，进行遍历对比
        while (slow != null && fast != null) {
            // 如果当前两个指针指向的节点值不相等，说明 slow 是安全的不重复节点，可以保留
            if (slow.val != fast.val) {
                copy.next = slow;         // 将 slow 接到结果链表中
                copy = copy.next;         // 更新结果链表的尾指针
                slow = slow.next;         // 慢指针前进一步
                fast = fast.next;         // 快指针前进一步
            } else {
                // 如果值相等，说明进入了重复段
                // 内部循环：跳过所有与 slow 当前值相同的节点
                while (fast != null && slow.val == fast.val) {
                    slow = slow.next;
                    fast = fast.next;
                }
                // 因为 slow 目前指向的是重复段的最后一个节点，需要再向前一步，跳过整个重复段
                slow = slow.next;
                // 如果快指针还未空，同样再向前一步，准备进行下一步的扫描
                if (fast != null) {
                    fast = fast.next;
                }
            }
        }
        
        // 当循环结束时，如果是尾部出现重复节点被跳过，最终只剩一个孤立重复节点，这一步需要做最后的安全拼接
        copy.next = slow;
        
        // 返回虚拟头节点的下一个节点，即去重后的真实头节点
        return result.next;
    }

    // ================= 方法 2：单指针（前驱指针）法 =================
    public ListNode deleteDuplicates1(ListNode head) {
        // 基础边界判断
        if (head == null || head.next == null) {
            return head;
        }
        
        // 1. 创建哑节点（虚拟头节点），指向 head。
        // 作用：防止原链表头节点自身就是重复元素被删掉，导致无法返回新的头节点
        ListNode dummy = new ListNode(0, head);
        // cur：用于遍历的前驱指针，初始指向哑节点
        ListNode cur = dummy; 
        
        // 检查当前节点之后是否至少还有两个节点
        while (cur.next != null && cur.next.next != null) {
            // 如果当前节点的下个节点，和下下个节点的值相同，说明出现了重复段
            if (cur.next.val == cur.next.next.val) {
                // 记录当前这个重复的值
                int val = cur.next.val;
                // 内部循环：只要下个节点不为空，且它和记录的值相同
                // 就不断将 cur.next 指向 cur.next.next，即跳过（删除）这个重复节点
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                // 如果不重复，前驱指针正常向后移动一位
                cur = cur.next;
            }
        }
        // 返回虚拟头节点的下一个节点，即处理后的新头节点
        return dummy.next;
    }
}