LeetCode: 83. Remove Duplicates from Sorted List

题目描述

Given a sorted linked list, delete all duplicates such that each element appear only once.

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

题目大意：删除已排序链表多余的节点，以使链表中的每一个元素只出现一次。

解题思路 —— 递归求解

本题类似于 LeetCode 82. Remove Duplicates from Sorted List II, 解题思路同 LeetCode: 82. Remove Duplicates from Sorted List II。只需要将删除当前节点的代码注释掉即可。

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;
            }

            // 删除掉当前节点(Remove Duplicates from Sorted List II)
            // ListNode* tmp = head;
            // head = head->next;
            // delete tmp;
        }

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

        return head;
    }
};