82.删除排序链表中的重复元素 II

题目:82.删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

• 示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

• 示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

• 提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

思路

要从已排序的链表中删除所有重复数字的节点，并只留下不同的数字，可以通过一次遍历链表来完成。这种方法使用了一个双指针技巧来追踪链表节点，删除所有出现重复的节点。

双指针法: 使用两个指针，一个指向当前节点，另一个指向前一个节点。当发现重复元素时，将前一个节点的 next 指针跳过所有重复的节点，直接指向下一个不重复的节点。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public ListNode deleteDuplicates(ListNode head) {
    ListNode result = new ListNode(0);
    result.next = head;
    // 定义前一个节点resultCurrent和当前节点current
    ListNode resultCurrent = result;
    ListNode current = head;
    while (current != null) {
        // 检查当前节点与下一个节点是否有相同的值
        if (current.next != null && current.val == current.next.val) {
            // 跳过所有具有相同值的节点
            while (current.next != null && current.val == current.next.val) {
                current = current.next;
            }
            // 将resultCurrent的next指向当前节点的下一个节点，跳过重复节点
            resultCurrent.next = current.next;
        } else {
            resultCurrent = resultCurrent.next;
        }
        // 移动current指针到下一个节点
        current = current.next;
    }
    return result.next;
}