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

分析

方法一：迭代法

我们可以使用两个指针来遍历链表。一个指针 prev 用于追踪当前节点的前一个节点，另一个指针 curr 用于遍历链表。当 curr 所指向的节点与下一个节点重复时，我们将 curr 向前移动直到它不再指向重复的节点。然后，我们更新 prev 的 next 指针，使其跳过重复的节点，指向 curr 指向的非重复节点。最后，我们更新 curr 指针和 prev 指针以继续遍历链表。

Java代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode curr = head;
    while (curr != null) {
        if (curr.next != null && curr.val == curr.next.val) {
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
            }
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
        curr = curr.next;
    }
    return dummy.next;
}

方法二：递归法

我们可以递归地解决这个问题。我们检查当前节点是否与下一个节点重复。如果是，我们继续遍历链表，直到找到第一个不重复的节点。然后，我们递归地处理剩余的链表并将结果链接回当前节点。

Java代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    if (head.val == head.next.val) {
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
        }
        return deleteDuplicates(head.next);
    } else {
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

方法三：计数法

我们可以使用一个辅助字典来统计每个节点的出现次数。然后，我们可以再次遍历链表，将所有出现次数为 1 的节点链接起来，构成一个新的链表。

Java代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }
    Map<Integer, Integer> map = new HashMap<>();
    ListNode curr = head;
    while (curr != null) {
        int count = map.getOrDefault(curr.val, 0);
        map.put(curr.val, count + 1);
        curr = curr.next;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;