LeetCode 82.Remove Duplicates from Sorted List II (删除排序链表中的重复元素 II)

喜欢ヅ旅行 2022-05-10 10:10 159阅读 0赞

题目描述：

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 *没有重复出现* 的数字。

**示例 1:**

输入: 1->2->3->3->4->4->5
    输出: 1->2->5

**示例 2:**

输入: 1->1->1->2->3
    输出: 2->3

AC C++ Solution:  
1.递归解决方法：  
递归基为head->next = NULL;

class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head) return 0;
            if (!head->next) return head;
            
            int val = head->val;
            ListNode* p = head->next;
            
            if (p->val != val) {
                head->next = deleteDuplicates(p);
                return head;
            } else {
                while (p && p->val == val) p = p->next;
                return deleteDuplicates(p);
            }
        }
    };

class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode **runner = &head;
            
            if(!head || !head->next)return head;
            
            while(*runner)
            {
                if((*runner)->next && (*runner)->next->val == (*runner)->val)
                {
                    ListNode *temp = *runner;
                    while(temp && (*runner)->val == temp->val)
                        temp = temp->next;
                    
                    *runner = temp;
                }
                else
                    runner = &((*runner)->next);
            }
            
            return head;
        }
    };