题⽬描述
在⼀个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输⼊：{1,2,3,3,4,4,5}
返回值：{1,2,5}
思路及解答
hash统计
第一次遍历统计频率，第二次遍历删除重复节点
import java.util.HashMap;public class Solution {public ListNode deleteDuplication(ListNode head) {if (head == null || head.next == null) {return head;}// 第一次遍历：统计每个节点值出现的次数HashMap<Integer, Integer> countMap = new HashMap<>();ListNode current = head;while (current != null) {countMap.put(current.val, countMap.getOrDefault(current.val, 0) + 1);current = current.next;}// 第二次遍历：删除重复节点ListNode dummy = new ListNode(-1); // 哑节点简化边界处理dummy.next = head;ListNode prev = dummy;current = head;while (current != null) {if (countMap.get(current.val) > 1) {// 当前节点重复，跳过prev.next = current.next;} else {// 当前节点不重复，移动prev指针prev = prev.next;}current = current.next;}return dummy.next;}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
直接遍历（推荐）
注意，题目已经提到是排序的节点，那么就可以直接原地删除
对⽐前后两个元素，如果相同的情况下，接着遍历后⾯的元素，直到元素不相等的时候，将前⾯的指针指向最后⼀个相同的元素的后⾯，相当于跳过了相同的元素。
public class Solution {public ListNode deleteDuplication(ListNode pHead){//遍历链表，直接删除if(pHead == null || pHead.next == null) return pHead;ListNode head = new ListNode(0);head.next = pHead;ListNode cur = head.next;ListNode pre = head;while(cur != null){//将重复的结点都遍历过，然后将后面节点复制给pre结点后面if(cur.next != null && cur.val == cur.next.val){while(cur.next != null && cur.val == cur.next.val){cur = cur.next;}pre.next = cur.next;cur = cur.next;}else{pre = pre.next;cur = cur.next;}}return head.next;}
}
- 空间复杂度为 O(1) ，没有借助额外的空间
- 时间复杂度为 O(n) ，只遍历了⼀次链表
递归
将大问题分解为当前节点+剩余链表的子问题
/*** 递归法：分治思想解决子问题* 思路：将大问题分解为当前节点+剩余链表的子问题* */
public class Solution {public ListNode deleteDuplication(ListNode head) {// 递归终止条件：空链表或单节点链表if (head == null || head.next == null) {return head;}// 情况1：当前节点与下一节点重复if (head.val == head.next.val) {// 跳过所有重复节点，找到第一个不重复的节点ListNode node = head.next;while (node != null && head.val == node.val) {node = node.next;}// 递归处理剩余部分return deleteDuplication(node);} // 情况2：当前节点不重复else {head.next = deleteDuplication(head.next);return head;}}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n) ，递归栈空间
三指针法
使用pre、cur、next三个指针精确控制删除范围
public class Solution {public ListNode deleteDuplication(ListNode head) {if (head == null || head.next == null) {return head;}ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy; // 前驱指针ListNode cur = head; // 当前指针ListNode next = null; // 后继指针while (cur != null && cur.next != null) {next = cur.next;// 发现重复节点if (cur.val == next.val) {// 移动next直到找到不重复的节点while (next != null && cur.val == next.val) {next = next.next;}// 跳过所有重复节点pre.next = next;cur = next;} // 没有重复，正常移动指针else {pre = cur;cur = cur.next;}}return dummy.next;}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)