https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
链表声明：
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
一次遍历
-
每次判断后面一个节点和后两个节点的值是否相同，相同则循环一直把后面的节点删干净，否则直接让游标向后移到。
-
dummyHead 解决繁杂的逻辑判断。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode dummyHead = new ListNode(0, head);
ListNode curNode = dummyHead; // curNode start from dummyHead
// there are at least two node after current node
while (curNode.next != null && curNode.next.next != null) {
if (curNode.next.val == curNode.next.next.val) {
int num = curNode.next.val;
// delete node which has same num
while (curNode.next != null && curNode.next.val == num) {
curNode.next = curNode.next.next;
}
} else {
curNode = curNode.next;
}
}
return dummyHead.next;
}
}
递归
-
把
deleteDuplicates(ListNode head)
的功能定义为：
删除 head 为首的链表中重复的节点
-
退出条件：
if (head == null || head.next == null) return head;
-
遇到当前 head 值跟下一个节点值相同，则让 head
跳过
这些相同值的节点。然后再递归对后面的元素递归处理
-
不相同，则直接让后面
处理好的
链表接到当前 head 上，然后返回。
head.next = deleteDuplicates(head.next);
public class Solution {
// Recursion Solution
public ListNode deleteDuplicates2(ListNode head) {
if (head == null || head.next == null) return head;
if (head.val == head.next.val) {
// equals jump the same node, then recursion the next node to operate behind listNode
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
// now Head is the last of the same nodes, so recursion object is head.next
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
return head;
}
}
}
