LeetCode: 82. Remove Duplicates from Sorted List II

题目描述

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目大意： 筛选出已排序链表中只出现一次的元素。

解题思路 —— 递归求解

1. 判断当前节点的元素是否只出现一次, 如果是, 则进入第三步；否则进行第二步。
2. 依次删除跟当前节点元素相等的节点，然后删除掉当前节点。进入第三步。
3. 对当前节点的 next 节点进行第一步的操作。

AC 代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        // 判断当前节点的元素是否只出现一次,
        while(head != nullptr && head->next != nullptr && head->val == head->next->val)
        {
            // 依次删除跟当前节点元素相等的节点
            while(head != nullptr && head->next != nullptr && head->val == head->next->val)
            {
                ListNode* tmp = head->next;
                head->next = head->next->next;
                delete tmp;
            }

            // 删除掉当前节点
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 对当前节点的 next 节点进行同样的操作
        if(head != nullptr)
        {
            head->next =  deleteDuplicates(head->next);
        }

        return head;
    }
};