Skip to main content

删除链表中的重复元素Ⅱ

· 5 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——82题​

💡 参考代码：​

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 删除已排序链表中的重复元素，只保留不重复的节点
 * 
 * @param head 链表头节点指针
 * @return 返回处理后的链表头节点指针
 * 
 * 解题思路:
 * 1. 使用虚拟头节点简化边界处理
 * 2. 用两个指针pre和cur分别指向已处理部分的最后一个节点和当前待处理节点
 * 3. 当发现重复节点时，跳过所有相同值的节点
 * 4. 时间复杂度: O(n), 空间复杂度: O(1)
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    // 创建虚拟头节点，简化对原头节点的处理
    struct ListNode dummy;
    dummy.next = head;
    
    // pre指向已处理部分的最后一个节点
    struct ListNode* pre = &dummy;
    // cur指向当前处理的节点
    struct ListNode* cur = head;
    
    while (cur != NULL && cur->next != NULL) {
        // 如果当前节点与下一个节点值相同，说明需要删除重复节点
        if (cur->val == cur->next->val) {
            int val = cur->val;  // 记录重复的值
            
            // 跳过所有值为val的节点
            while (cur != NULL && cur->val == val) {
                struct ListNode* temp = cur;
                cur = cur->next;
                free(temp);  // 释放被删除节点的内存
            }
            
            // 将pre的next指向cur，即跳过所有重复节点
            pre->next = cur;
        } else {
            // 没有重复，正常移动指针
            pre = cur;
            cur = cur->next;
        }
    }
    
    // 返回处理后链表的头节点
    return dummy.next;
}

📖 总结：​

点击展开题目总结

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

1️⃣ 题目核心信息​

🎯 功能描述：删除已排序链表中所有重复数字的节点，只保留不重复的数字

📥 输入输出：

  • 输入：head - 已排序链表的头节点指针
  • 输出：返回处理后的链表头节点指针

2️⃣ 实现原理​

💡 核心思路：使用双指针遍历链表，当发现重复元素时跳过所有相同值的节点

📋 实现步骤：

  1. 创建虚拟头节点简化边界处理
  2. 使用pre指针指向已处理部分的最后一个节点
  3. 使用cur指针遍历链表
  4. 当发现重复节点时，跳过所有相同值的节点

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用虚拟头节点(dummy)简化对原头节点的处理
  • 双指针法(pre和cur)有效管理链表连接关系
  • 记录重复值并一次性跳过所有相同节点

4️⃣ 使用场景​

✅ 适用情况：​

  • 处理已排序的链表去重问题
  • 需要完全删除重复元素而非保留一个
  • 链表操作相关的问题

⚠️ 前提条件：​

  • 链表已按升序排列
  • 节点值在[-100, 100]范围内

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n) - 每个节点最多被访问一次
  • 💾 空间复杂度：O(1) - 只使用了常数额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 空链表或只有一个节点
  • 所有节点值都相同
  • 头节点本身就是重复节点

💥 易错点：​

  • 忘记释放被删除节点的内存
  • 处理头节点重复时的边界情况
  • 没有正确更新pre指针的连接关系

7️⃣ 补充说明​

这道题与"删除排序链表中的重复元素I"的区别在于需要完全删除重复元素，而不是保留一个。使用虚拟头节点可以大大简化代码逻辑，避免对头节点的特殊处理。

📚 逐步执行示例​

通过示例1来逐步解释算法执行过程：head = [1,2,3,3,4,4,5]

步骤1：初始化​

dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> NULL
pre
       cur

步骤2：处理节点1​

  • cur->val(1) != cur->next->val(2)，无重复
  • pre = cur, cur = cur->next
dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> NULL
         pre
              cur

步骤3：处理节点2​

  • cur->val(2) != cur->next->val(3)，无重复
  • pre = cur, cur = cur->next
dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> NULL
              pre
                   cur

步骤4：处理重复节点3​

  • cur->val(3) == cur->next->val(3)，发现重复
  • 记录val = 3，跳过所有值为3的节点
  • pre->next = cur (此时cur指向第一个值为4的节点)
dummy -> 1 -> 2 -> 4 -> 4 -> 5 -> NULL
                   pre
                        cur

步骤5：处理重复节点4​

  • cur->val(4) == cur->next->val(4)，发现重复
  • 记录val = 4，跳过所有值为4的节点
  • pre->next = cur (此时cur指向值为5的节点)
dummy -> 1 -> 2 -> 5 -> NULL
                   pre
                        cur

步骤6：处理节点5​

  • cur->next == NULL，循环结束

最终结果​

返回 dummy.next，即链表 [1,2,5]

加载评论中...