Remove Duplicates from Sorted List trong C++

Cho danh sách liên kết đã sắp xếp, xóa các nút trùng lặp để mỗi giá trị chỉ xuất hiện một lần.

Ví dụ: 1→1→2→3→3→3→4→5→5 → 1→2→3→4→5.

Giải thuật

Duyệt danh sách, nếu nút hiện tại và nút tiếp theo cùng giá trị → bỏ qua nút tiếp theo (curr->next = curr->next->next).

Ví dụ triển khai C++

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

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

// Helper
ListNode* build(vector<int> v) {
    if (v.empty()) return nullptr;
    ListNode* head = new ListNode(v[0]);
    ListNode* cur = head;
    for (int i = 1; i < v.size(); i++) {
        cur->next = new ListNode(v[i]);
        cur = cur->next;
    }
    return head;
}

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

int main() {
    Solution ob;
    vector<int> v = {1,1,2,3,3,3,4,5,5};
    print(ob.deleteDuplicates(build(v))); // [1, 2, 3, 4, 5]
    return 0;
}

Đầu vào / Đầu ra

Input: {1,1,2,3,3,3,4,5,5}
Output: [1, 2, 3, 4, 5]