Java怎么删除链表中重复的结点

# Java怎么删除链表中重复的结点

## 目录
1. [链表与重复结点问题概述](#链表与重复结点问题概述)
2. [基础解法：双重循环遍历](#基础解法双重循环遍历)
3. [哈希表优化解法](#哈希表优化解法)
4. [排序后处理法](#排序后处理法)
5. [递归解法](#递归解法)
6. [不同解法对比与选择](#不同解法对比与选择)
7. [完整代码示例](#完整代码示例)
8. [边界条件与注意事项](#边界条件与注意事项)
9. [扩展应用场景](#扩展应用场景)

---

## 链表与重复结点问题概述
链表是一种常见的基础数据结构，由一系列结点组成，每个结点包含数据域和指针域。在实际开发中，我们经常需要处理链表中存在重复结点的情况，例如：
- 用户行为日志去重
- 商品浏览记录清理
- 网络请求去重处理

**示例链表：**

1 → 3 → 3 → 5 → 7 → 7 → null

删除重复结点后应变为：

1 → 3 → 5 → 7 → null

---

## 基础解法：双重循环遍历
### 时间复杂度：O(n²)
```java
public ListNode removeDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null) {
        ListNode runner = current;
        while (runner.next != null) {
            if (runner.next.val == current.val) {
                runner.next = runner.next.next; // 跳过重复结点
            } else {
                runner = runner.next;
            }
        }
        current = current.next;
    }
    return head;
}

实现要点： 1. 外层循环遍历每个结点作为基准 2. 内层循环比较后续所有结点 3. 发现重复时修改指针跳过

适用场景： - 内存受限环境 - 小规模数据（n < 1000）

哈希表优化解法

时间复杂度：O(n) | 空间复杂度：O(n)

public ListNode removeDuplicatesWithHash(ListNode head) {
    Set<Integer> seen = new HashSet<>();
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        if (seen.contains(curr.val)) {
            prev.next = curr.next; // 删除当前结点
        } else {
            seen.add(curr.val);
            prev = curr;
        }
        curr = curr.next;
    }
    return head;
}

优势分析： - 时间复杂度显著降低 - 代码可读性更好 - 适合处理大规模数据

内存消耗： - 需要额外存储n个元素的哈希表 - JDK中HashSet每个元素占用约16字节

排序后处理法

时间复杂度：O(nlogn)

public ListNode removeDuplicatesAfterSort(ListNode head) {
    if (head == null) return null;
    
    // 排序链表（可使用归并排序）
    head = sortList(head);
    
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

特点： - 先排序后去重只需单次遍历 - 排序操作会增加时间复杂度 - 可能改变原始链表顺序

适用场景： - 后续需要有序链表的场景 - 允许修改结点顺序的情况

递归解法

public ListNode removeDuplicatesRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    head.next = removeDuplicatesRecursive(head.next);
    
    return head.val == head.next.val ? head.next : head;
}

递归栈分析： - 最大递归深度 = 链表长度 - 存在栈溢出风险（约10000+结点） - 代码简洁但调试困难

优化建议： - 添加尾递归优化（需语言支持） - 限制递归深度

不同解法对比与选择

选择建议： 1. 面试场景优先选择哈希表解法 2. 嵌入式环境考虑双重循环 3. 已排序数据直接使用单次遍历

完整代码示例

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class LinkedListDedup {
    
    // 方法1：双重循环
    public static ListNode method1(ListNode head) {
        // 实现代码见前文
    }
    
    // 方法2：哈希表
    public static ListNode method2(ListNode head) {
        // 实现代码见前文
    }
    
    public static void main(String[] args) {
        // 构建测试链表：1->3->3->5
        ListNode head = new ListNode(1);
        head.next = new ListNode(3);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(5);
        
        // 测试不同方法
        printList(method1(head));
        printList(method2(head));
    }
    
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}

边界条件与注意事项

1. 空链表处理：

   if (head == null) return null;
   

2. 全重复链表：

   输入：2→2→2→2
   输出：2
   

3. 内存泄漏问题：

   • 在C++等需要手动管理内存的语言中要注意释放被删除结点
   • Java的GC会自动处理

4. 大整数处理：

   • 当结点值非常大时，哈希表可能产生哈希冲突
   • 可考虑使用BitSet或布隆过滤器

扩展应用场景

1. 对象链表去重： “`java class User { int id; String name; // 重写equals和hashCode }

Set userSet = new HashSet<>();

2. **多条件去重**：
   ```java
   // 使用复合键
   record Key(int field1, String field2) {}
   Set<Key> dedupSet = new HashSet<>();

1. 分布式环境处理：

   • 使用Redis等外部存储维护去重集合
   • 考虑采用分区哈希策略

2. 流式数据处理：

   // 使用流式API处理
   list.stream().distinct().collect(Collectors.toList());
   

总结：本文详细探讨了4种Java实现链表去重的方法，每种方法各有优缺点。实际开发中应根据数据规模、内存限制、性能要求等因素选择合适方案。对于面试场景，建议至少掌握哈希表和双重循环两种解法。 “`

这篇文章包含了约2900字内容，采用Markdown格式编写，包含： 1. 多种实现方法的代码示例 2. 复杂度分析和比较表格 3. 实际应用场景说明 4. 边界条件处理建议 5. 扩展知识补充

可以通过调整代码示例的详细程度或增加更多应用案例来进一步扩展内容。