DeepSeek LeetCode 82. 删除排序链表中的重复元素 II Java实现

LeetCode 82「删除排序链表中的重复元素 II」要求删除所有重复的节点，只保留没有重复出现的数字。下面给出 Java 实现，使用哑节点简化头节点处理。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */classSolution{publicListNodedeleteDuplicates(ListNodehead){// 哑节点，方便处理头节点可能被删除的情况ListNodedummy=newListNode(0);dummy.next=head;ListNodeprev=dummy;// prev 始终指向已保留部分的最后一个节点ListNodecurr=head;// curr 为当前待检查的节点while(curr!=null){// 如果当前节点与下一个节点值相同，说明有重复if(curr.next!=null&&curr.val==curr.next.val){intduplicateVal=curr.val;// 跳过所有值为 duplicateVal 的节点while(curr!=null&&curr.val==duplicateVal){curr=curr.next;}// 将 prev 的下一个节点指向第一个不同值的节点prev.next=curr;}else{// 当前节点不重复，保留它，prev 和 curr 都前移prev=curr;curr=curr.next;}}returndummy.next;}}

思路说明：

· 使用哑节点 dummy 指向链表头，prev 指向已处理部分的末尾，初始为 dummy。
· 遍历链表，当发现当前节点 curr 与下一个节点值相同，记录该重复值，然后内层循环跳过所有等于该值的节点。
· 跳过重复节点后，prev.next 直接指向第一个值不同的节点（即 curr），但 prev 本身不移动，因为需要继续检查新的 curr 是否重复。
· 如果当前节点不重复，则 prev 和 curr 均前移。
· 最终返回 dummy.next，即去重后的链表头。

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