1+ // 82. 删除排序链表中的重复元素 II
2+
3+
4+ /**
5+ * Definition for singly-linked list.
6+ * public class ListNode {
7+ * int val;
8+ * ListNode next;
9+ * ListNode() {}
10+ * ListNode(int val) { this.val = val; }
11+ * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
12+ * }
13+ */
14+
15+
16+ /*
17+ 递归：
18+ 1、方法功能：入参是一个节点，判断该节点是否重复，不重复则返回该节点，否则往下遍历找到第一个与该节点不相同的节点后返回
19+ 2、终止条件：节点为空 或 下一节点为空，则直接返回，因为至少需要两个节点才需要判断删除
20+ 3、递归逻辑：先根据一个节点的情况进行处理，处理完后下一节点同样需要判断处理，则调用同样的方法递归处理
21+ */
22+ class Solution {
23+ public ListNode deleteDuplicates (ListNode head ) {
24+ if (head == null || head .next == null ) {
25+ return head ;
26+ }
27+ if (head .val != head .next .val ) {
28+ head .next = deleteDuplicates (head .next );
29+ return head ;
30+ } else {
31+ ListNode temp = head .next ;
32+ while (temp != null && head .val == temp .val ) {
33+ temp = temp .next ;
34+ }
35+ return deleteDuplicates (temp );
36+ }
37+ }
38+ }
39+
40+
41+ /*
42+ 一次遍历，改变节点指针：
43+ 1、至少要有两个节点才需要判断删除，否则直接返回
44+ 2、初始化pre、cur的位置，两者相邻。pre表示前一个有效节点的指针
45+ 3、当cur下一节点值与当前相同时，则cur继续往右走，走到最后一个值相同的节点
46+ 4、如果pre下一节点还是cur，说明中间没有重复节点，pre往右走一步即可。
47+ 如果pre下一节点不是cur，说明中间有重复节点，包括cur在内的节点都要删除，即pre下一指针指向cur下一指针节点。此时pre还不能动，因为新的cur可能还是重复节点
48+ 5、经过一轮判断处理后，cur往右走一步。此时pre、cur回到初始状态
49+
50+ 0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
51+ root/pre cur
52+ ===========================================================
53+ 0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
54+ root pre cur
55+ ===========================================================
56+ 0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
57+ root pre cur
58+ ===========================================================
59+ 0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
60+ root pre cur
61+ ===========================================================
62+ 0 → 1 → 2 → 4 → 4 → 5
63+ root pre cur
64+ ===========================================================
65+ 0 → 1 → 2 → 4 → 4 → 5
66+ root pre cur
67+ ===========================================================
68+ 0 → 1 → 2 → 5
69+ root pre cur
70+ ===========================================================
71+ 0 → 1 → 2 → 5
72+ root pre cur
73+ */
74+ class Solution {
75+ public ListNode deleteDuplicates (ListNode head ) {
76+ if (head == null || head .next == null ) {
77+ return head ;
78+ }
79+ ListNode root = new ListNode (0 , head );
80+ ListNode pre = root , cur = head ;
81+ while (cur != null ) {
82+ while (cur .next != null && cur .val == cur .next .val ) {
83+ cur = cur .next ;
84+ }
85+ if (pre .next == cur ) {
86+ pre = pre .next ;
87+ } else {
88+ pre .next = cur .next ;
89+ }
90+ cur = cur .next ;
91+ }
92+ return root .next ;
93+ }
94+ }
95+
96+
97+ /*
98+ 记录个数，改变节点指针：
99+ 1、上一解法是cur直接走到最后一个重复节点位置，一次性跳过多个重复节点
100+ 当前解法是cur一步一步走，根据map中记录的出现次数决定是否跳过cur节点
101+ 2、先遍历一次，记录每个节点值出现次数
102+ 3、再次遍历，如果节点出现次数大于1则跳过
103+ */
104+ class Solution {
105+ public ListNode deleteDuplicates (ListNode head ) {
106+ if (head == null || head .next == null ) {
107+ return head ;
108+ }
109+ Map <Integer , Integer > map = new HashMap <>();
110+ ListNode temp = head ;
111+ while (temp != null ) {
112+ map .put (temp .val , map .getOrDefault (temp .val , 0 ) + 1 );
113+ temp = temp .next ;
114+ }
115+ ListNode root = new ListNode (0 , head );
116+ ListNode pre = root , cur = head ;
117+ while (cur != null ) {
118+ if (map .get (cur .val ) == 1 ) {
119+ pre = pre .next ;
120+ } else {
121+ pre .next = cur .next ;
122+ }
123+ cur = cur .next ;
124+ }
125+ return root .next ;
126+ }
127+ }
0 commit comments