博文中会简要介绍Leetcode P0083题目分析及解题思路。
“Remove Duplicates from Sorted List”是一道比较简单的题目，思路和p0026十分相似，只是p0026是针对数组，而这道题是针对链表。
Given a sorted linked list, delete all duplicates such that each element appear only once.
核心思路是维护两个指针，right指针用于遍历，left指针用于指向right指针左边最后一个非元素的重复副本的结点。若right和left指针指向的元素值相同，则跳过该副本，right向后遍历，且left指针的next域指向向右遍历后的right指针所指向的结点。
以下是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 = head, right = head.next;
while (right != null) {
if (right.val == left.val) {
right = right.next;
left.next = right;
}
else {
right = right.next;
left = left.next;
}
}
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 = head, *right = head->next;
while (right != NULL) {
if (right->val == left->val) {
right = right->next;
left->next = right;
}
else {
right = right->next;
left = left->next;
}
}
return dummy->next;
}
};