LeetCode解题报告（260）-- 82. Remove Duplicates from Sorted List II

Problem

Given the head of 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.

Example 1:

1 2	Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]

Example 2:

1 2	Input: head = [1,1,1,2,3] Output: [2,3]

Constraints:

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

Analysis

这道题要求我们从一个链表中移除重复的元素。在之前我们遇到过数组中移除重复的元素，这里从数组变成了链表。从删除的角度来说，链表是比较方便的。我们用两个指针，一个pre指针指向当前元素的前一个，另一个cur指针指向当前元素，两个指针的作用就是用来跳过重复的数字。例如在Example 1中，当cur指向第一个3的时候，pre指向2。此时通过判断相同元素cur一直往后到第二个3，这个时候pre->next = cur->next就完成了相同元素的移除。

Solution

在判断是否需要移除时，通过判断cur是否和pre->next相等得知。在没有重复元素的情况下两者是相等的。

Code

/**
 * 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) {
        ListNode* dummy = new ListNode(-101);
        dummy->next = head;
        ListNode* pre = dummy;
        
        while (pre->next) {
            ListNode* current = pre->next;
            while (current->next && current->next->val == current->val) {
                current = current->next;
            }
            
            if (current != pre->next) {
                // skip duplicate element
                pre->next = current->next;
            } else {
                pre = pre->next;
            }
        }
        return dummy->next;
    }
};

Summary

这道题目是数组或链表中移除重复元素的系列题，也给了我们很好的思考。对于同样的问题，使用数组和链表求解的思路完全不一样。总体上说数组以交换操作居多，而链表以删除操作为主。这道题这道题目的分享到这里，谢谢您的支持！