Remove Duplicates from Sorted List II - ลบโหนดซ้ำทั้งหมดใน C++

ภาพรวมปัญหา

มี Linked List ที่จัดเรียงแล้ว ต้องลบโหนดที่มีค่าซ้ำออกทั้งหมด (เก็บเฉพาะค่าที่ไม่ซ้ำ)

ตัวอย่าง: [1,1,1,2,2,3,5,6,6,7,8] → [3,5,7,8]

อัลกอริทึม

1. สร้าง dummy node (val = -1), prev = NULL, dummyPtr = dummy
2. while head ไม่ใช่ null:
   • ถ้า head->next ว่าง หรือ head->val != head->next->val (ค่าไม่ซ้ำ):
     • dummyPtr->next = head
     • temp = head->next, head->next = NULL
     • head = temp, dummyPtr = dummyPtr->next
   • อื่นๆ (ค่าซ้ำ):
     • prev = head, head = head->next
     • while head ไม่ว่างและ head->val == prev->val: prev = head, head = head->next
3. return dummy->next

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class ListNode{
public:
    int val;
    ListNode *next;
    ListNode(int data){ val = data; next = NULL; }
};

ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i < v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = NULL;
        ListNode* dummyPtr = dummy;
        ListNode* nextNode;
        while(head){
            if(!head->next || head->val != head->next->val){
                dummyPtr->next = head;
                ListNode* temp = head->next;
                head->next = NULL;
                head = temp;
                dummyPtr = dummyPtr->next;
            } else {
                prev = head;
                head = head->next;
                while(head && head->val == prev->val){
                    prev = head;
                    head = head->next;
                }
            }
        }
        return dummy->next;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.deleteDuplicates(head));
}

Input / Output

Input:  [1,1,1,2,2,3,5,6,6,7,8]
Output: [3, 5, 7, 8]