【Leetcode】82. Remove Duplicates from Sorted List II（链表）

喜欢ヅ旅行 2022-02-23 04:16 153阅读 0赞

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

**Example 1:**

Input: 1->2->3->3->4->4->5
    Output: 1->2->5

**Example 2:**

Input: 1->1->1->2->3
    Output: 2->3

题目大意：

删除已给字符串中相邻的重复数字

解题思路:

链表的做法需要格外注意，一开始是不是连续的，如果是的话需要调整头结点的位置，如果连续的在中间则只需要删除该区间即可。

/**
     * 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) {
            if(head==NULL) return head;
            bool state= false;
            vector<int> tmp;
            while(head){
                if(tmp.size()!=0&&head->val==tmp[tmp.size()-1]){
                    state = true;
                }else{
                    if(state == true){
                        tmp.pop_back();
                        state = false;
                        tmp.push_back(head->val);
                    }
                    else{
                        tmp.push_back(head->val);
                    }
                }
                if(head->next==NULL&&state){
                    tmp.pop_back();
                }
                head= head->next;
            }
            if(tmp.size()==0) return NULL;
            ListNode *l= new ListNode(tmp[0]);
            ListNode *r;
            r=l;
            for(int i=1;i<tmp.size();i++){
                ListNode *tmp1 = new ListNode(tmp[i]);
                l->next = tmp1;
                l = l->next;
            }
    
            return r;
        }
    };

/**
     * 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) {
            ListNode* t= head;
            ListNode* pre = head;
            while(head!=NULL){
                bool flag = false;
                while(head->next!=NULL && head->val == head->next->val){
                    ListNode* temp=head->next;
                    head->next = temp->next;
                    delete temp;
                    flag = true;
                }
                
                if(flag == false){
                    pre=head;
                    head=head->next;
                }
                else{
                    if(head==t&&head->next==NULL) return NULL;
                    else if(head==t&&head->next!=NULL){
                        t = head->next;
                        head = head->next;
                        pre = head;
                    }
                    else{
                        pre->next = head->next;
                        head = pre;
                    }
                }
            }
            return t;
        }
    };