题解 | 删除有序链表中重复的元素-II

1、解题思路

1. 使用哨兵节点：创建一个哨兵节点 dummy，将其 next 指向链表头，便于处理头节点可能被删除的情况。
2. 遍历链表：使用指针 prev 指向当前已处理链表的最后一个节点，curr 指向当前正在检查的节点。循环检查 curr 和 curr.next 是否相同： 若相同，则继续移动 curr 直到找到不同的节点，然后跳过所有重复节点。若不同，则移动 prev 到 curr，表示当前节点保留。
3. 返回结果：返回 dummy.next，即处理后的链表头。

2、代码实现

C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        ListNode dummy(0), *prev = &dummy, *cur = head;
        dummy.next = head;

        while (cur) {
            // 检查当前节点是否有重复
            bool duplicate = false;
            while (cur->next != nullptr && cur->val == cur->next->val) {
                duplicate = true;
                cur = cur->next;
            }
            // 如果有重复, 跳过所有重复节点
            if (duplicate) {
                prev->next = cur->next;
            } else {
                prev = prev->next;
            }
            cur = cur->next;
        }

        return dummy.next;
    }
};

Java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;

        while (curr != null) {
            boolean duplicate = false;
            while (curr.next != null && curr.val == curr.next.val) {
                duplicate = true;
                curr = curr.next;
            }
            if (duplicate) {
                prev.next = curr.next;
            } else {
                prev = prev.next;
            }
            curr = curr.next;
        }

        return dummy.next;
    }
}

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(0)
        dummy.next = head
        prev, curr = dummy, head
        
        while curr:
            duplicate = False
            while curr.next and curr.val == curr.next.val:
                duplicate = True
                curr = curr.next
            if duplicate:
                prev.next = curr.next
            else:
                prev = prev.next
            curr = curr.next
        
        return dummy.next

3、复杂度分析

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