博文中会简要介绍Leetcode P0082题目分析及解题思路。
“Remove Duplicates from Sorted List II”是p0083的变形题。相对于其原型题，p0082的难度稍微有所提高。
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
该题的核心思路依旧是维护两个指针，左指针用于记录当前已经合法的链表末结点，而右指针用于遍历后续链表，除此之外再维护一个prev指针用于记录右指针前一个指针，来获取前一个元素的值，最后维护一个布尔值作为标志位，来标志是否跳过了副本。双指针移动条件如下：
left: 左指针
right: 右指针
prev: right前一个指针
flag: 布尔标志位
move right; move left; set flag, if right.val == prev.val
若当前right指针指向的元素值和前一个元素的值相同，则跳过该副本元素，并且将标志位置为true
move left, if flag is not set
若当前标志位为false，则说明当前right和prev的元素不同，且prev元素仅出现一次；若标志位是true，则说明前面跳过了重复元素，此时的left应当维持原位，让新的prev和right继续判断（新的prev和right有可能继续是重复元素）
prev = right; right = right.next; reset flag
移动相关指针，并且复位标志位。
以下是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; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode left = dummy, prev = head, right = head.next;
boolean isDupBefore = false;
while (right != null) {
if (right.val == prev.val) {
right = right.next;
left.next = right;
isDupBefore = true;
}
else {
if (!isDupBefore)
left = left.next;
prev = right;
right = right.next;
isDupBefore = false;
}
}
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL)
return head;
ListNode *dummy = new ListNode(0, head);
ListNode *left = dummy, *prev = head, *right = head->next;
bool is_duplicate_before = false;
while (right != NULL) {
if (prev->val == right->val) {
right = right->next;
left->next = right;
is_duplicate_before = true;
}
else {
if (!is_duplicate_before)
left = left->next;
prev = right;
right = right->next;
is_duplicate_before = false;
}
}
return dummy->next;
}
};