Variasi Pemecahan Masalah Linked List

Soal linked list klasik menguji pemahaman pointer dan pola algoritma. Tiga di antaranya muncul berulang di interview dan kompetisi: mengecek apakah list adalah palindrome, menghapus node ke-N dari belakang, dan menemukan titik perpotongan dua list. Pada Chapter ini kita akan membedah ketiganya dengan pendekatan pointer-based yang efisien — semua O(n) time dan O(1) space — serta membahas trik yang membuat solusi elegan. Setiap pola akan menambah “vocabulary” algoritma linked list kita.

Pola 1: Palindrome Check (One Pass, O(1) Space) #

Aturan #

Diberikan head singly linked list, tentukan apakah list tersebut palindrome — elemen dibaca sama dari depan maupun belakang.

Mekanisme: Reverse First Half In-Place #

Pendekatan naif: salin list ke std::vector, bandingkan dari dua ujung — O(n) time, O(n) space. Pendekatan efisien memakai slow/fast pointer:

Cari middle dengan slow/fast — sambil reverse first half in-place.
Setelah loop, prev menunjuk ke head dari first half yang sudah terbalik.
Bandingkan prev (reversed first half) dengan slow (second half).
(Opsional) restore first half — skip di demo.

Kode: Palindrome Check #

cpp
bool is_palindrome(Node<int>* head) {
    if (head == nullptr || head->next == nullptr) return true;
    // Cari middle dengan slow/fast
    Node<int>* slow = head;
    Node<int>* fast = head;
    Node<int>* prev = nullptr;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        Node<int>* nx = slow->next;
        slow->next = prev;   // reverse first half sambil jalan
        prev = slow;
        slow = nx;
    }
    // Bila panjang ganjil, slow di middle; skip middle
    if (fast != nullptr) slow = slow->next;
    // Bandingkan prev (first half reversed) dan slow (second half)
    Node<int>* p1 = prev;
    Node<int>* p2 = slow;
    bool ok = true;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->nilai != p2->nilai) { ok = false; break; }
        p1 = p1->next;
        p2 = p2->next;
    }
    return ok;
}

Line-by-line #

Node<int>* prev = nullptr;: awal reverse first half. Sama seperti reverse iteratif, prev berjalan dari nullptr ke node pertama yang dibalik.
slow->next = prev; (di dalam loop): reverse terjadi sambil slow berjalan. Setelah loop, first half sudah terbalik, dengan prev sebagai head baru (reversed).
if (fast != nullptr) slow = slow->next;: bila panjang ganjil, fast berakhir di node terakhir (bukan nullptr). Middle node tidak perlu dibandingkan — skip.
while (p1 != nullptr && p2 != nullptr): bandingkan elemen demi elemen. Karena first half sudah dibalik, traversal prev ke depan = traversal list dari tengah ke awal.
Kompleksitas: O(n) time, O(1) space. In-place, tanpa alokasi.

Pola 2: Remove Nth Node From End #

Aturan #

Diberikan head linked list dan integer n, hapus node ke-n dari belakang. Soal klasik LeetCode #19.

Mekanisme: Two Pointers dengan Jarak N+1 #

Pendekatan naif: hitung panjang L, lalu hapus node ke-L-n+1 dari depan — dua pass, O(n) time, O(1) space. Pendekatan satu pass memakai two pointers dengan jarak tetap n+1:

Buat dummy node, dummy.next = head — agar kasus hapus head tertangani seragam.
Majukan first sebanyak n+1 langkah.
Majukan first dan second bersamaan sampai first == nullptr.
Sekarang second->next adalah node ke-n dari belakang — hapus.

cpp
Node<int>* remove_nth_from_end(Node<int>* head, int n) {
    Node<int> dummy(0);
    dummy.next = head;
    Node<int>* first = &dummy;
    Node<int>* second = &dummy;
    // Maju first n+1 langkah
    for (int i = 0; i <= n; ++i) first = first->next;
    // Maju keduanya sampai first sampai null
    while (first != nullptr) {
        first = first->next;
        second = second->next;
    }
    // second->next adalah node yang akan dihapus
    Node<int>* to_delete = second->next;
    second->next = second->next->next;
    delete to_delete;
    return dummy.next;
}

Line-by-line #

Node<int> dummy(0); dummy.next = head;: dummy node dengan nilai default. Menangani kasus hapus head — bila n == length, second akan berakhir di dummy, dan second->next adalah head asli.
for (int i = 0; i <= n; ++i) first = first->next;: majukan first sebanyak n+1 langkah. Setelah ini, jarak first dan second adalah n+1.
while (first != nullptr) { first = first->next; second = second->next; }: kedua pointer maju bersamaan. Saat first mencapai nullptr, second->next adalah node ke-n dari belakang.
second->next = second->next->next;: lompati node yang akan dihapus — sambung ulang chain.
delete to_delete;: bebaskan memori node yang dihapus.
return dummy.next;: head mungkin berubah (bila yang dihapus adalah head asli). dummy.next selalu menunjuk ke head baru.

Kompleksitas: O(n) time, O(1) space. Satu pass tanpa menghitung panjang eksplisit.

Pola 3: Intersection of Two Linked Lists #

Aturan #

Diberikan dua singly linked list yang mungkin berpotongan di suatu node (lalu berbagi tail yang sama), temukan node perpotongan pertama. Soal LeetCode #160.

Mekanisme: Samakan Panjang dengan Offset #

Pendekatan naif: hash set menyimpan node yang dikunjungi list A, lalu cek setiap node di list B — O(n+m) time, O(n) space. Pendekatan efisien:

Hitung panjang kedua list.
Maju list lebih panjang selisih panjangnya — keduanya sekarang punya sisa panjang yang sama.
Traverse keduanya bersamaan, cek kesetaraan pointer.

cpp
int length(Node<int>* head) {
    int n = 0;
    while (head != nullptr) { ++n; head = head->next; }
    return n;
}

Node<int>* get_intersection(Node<int>* a, Node<int>* b) {
    int la = length(a), lb = length(b);
    // Maju list lebih panjang selisihnya
    while (la > lb) { a = a->next; --la; }
    while (lb > la) { b = b->next; --lb; }
    while (a != nullptr && b != nullptr) {
        if (a == b) return a;
        a = a->next;
        b = b->next;
    }
    return nullptr;
}

Line-by-line #

int la = length(a), lb = length(b);: dua pass untuk hitung panjang. Total tetap O(n+m).
while (la > lb) { a = a->next; --la; }: list A lebih panjang — maju selisihnya. Setelah ini, sisa panjang A = sisa panjang B.
while (a != nullptr && b != nullptr) { if (a == b) return a; ... }: traverse bersamaan, cek pointer equality (bukan nilai equality). Perpotongan = kedua list berbagi node yang sama, bukan hanya nilai yang sama.
return nullptr;: tidak ada perpotongan — kembalikan nullptr.

Kompleksitas: O(n+m) time, O(1) space. Dua pass untuk panjang, satu pass untuk perbandingan.

Kode Lengkap Tiga Pola #

cpp
#include <iostream>
#include <vector>

template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

// 1. Palindrome check: bandingkan dengan stack virtual (reverse first half)
bool is_palindrome(Node<int>* head) {
    if (head == nullptr || head->next == nullptr) return true;
    // Cari middle dengan slow/fast
    Node<int>* slow = head;
    Node<int>* fast = head;
    Node<int>* prev = nullptr;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        Node<int>* nx = slow->next;
        slow->next = prev;   // reverse first half sambil jalan
        prev = slow;
        slow = nx;
    }
    // Bila panjang ganjil, slow di middle; skip middle
    if (fast != nullptr) slow = slow->next;
    // Bandingkan prev (first half reversed) dan slow (second half)
    Node<int>* p1 = prev;
    Node<int>* p2 = slow;
    bool ok = true;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->nilai != p2->nilai) { ok = false; break; }
        p1 = p1->next;
        p2 = p2->next;
    }
    // (Optional) restore first half — di-skip di demo
    return ok;
}

// 2. Remove nth from end: two-pass singkat dengan dummy head
Node<int>* remove_nth_from_end(Node<int>* head, int n) {
    Node<int> dummy(0);
    dummy.next = head;
    Node<int>* first = &dummy;
    Node<int>* second = &dummy;
    // Maju first n+1 langkah
    for (int i = 0; i <= n; ++i) first = first->next;
    // Maju keduanya sampai first sampai null
    while (first != nullptr) {
        first = first->next;
        second = second->next;
    }
    // second->next adalah node yang akan dihapus
    Node<int>* to_delete = second->next;
    second->next = second->next->next;
    delete to_delete;
    return dummy.next;
}

// 3. Intersection point: dapat panjang, mulai dari offset
int length(Node<int>* head) {
    int n = 0;
    while (head != nullptr) { ++n; head = head->next; }
    return n;
}

Node<int>* get_intersection(Node<int>* a, Node<int>* b) {
    int la = length(a), lb = length(b);
    // Maju list lebih panjang selisihnya
    while (la > lb) { a = a->next; --la; }
    while (lb > la) { b = b->next; --lb; }
    while (a != nullptr && b != nullptr) {
        if (a == b) return a;
        a = a->next;
        b = b->next;
    }
    return nullptr;
}

// Helper untuk demo
template <typename T>
Node<T>* make_list(const std::vector<T>& vals) {
    Node<T>* h = nullptr;
    Node<T>* t = nullptr;
    for (const T& v : vals) {
        Node<T>* n = new Node<T>(v);
        if (h == nullptr) h = t = n;
        else { t->next = n; t = n; }
    }
    return h;
}

void print_list(Node<int>* h, const std::string& label) {
    std::cout << label << ": ";
    while (h != nullptr) {
        std::cout << h->nilai << (h->next ? " -> " : " -> null\n");
        h = h->next;
    }
}

void free_list(Node<int>* h) {
    while (h != nullptr) { Node<int>* n = h->next; delete h; h = n; }
}

int main() {
    // 1. Palindrome
    Node<int>* p1 = make_list<int>({1, 2, 3, 2, 1});
    Node<int>* p2 = make_list<int>({1, 2, 3, 4, 5});
    Node<int>* p3 = make_list<int>({1, 2, 2, 1});
    std::cout << "palindrome {1,2,3,2,1}: " << std::boolalpha << is_palindrome(p1) << '\n';
    std::cout << "palindrome {1,2,3,4,5}: " << is_palindrome(p2) << '\n';
    std::cout << "palindrome {1,2,2,1}   : " << is_palindrome(p3) << '\n';
    free_list(p1); free_list(p2); free_list(p3);

    // 2. Remove nth from end
    Node<int>* r = make_list<int>({1, 2, 3, 4, 5});
    print_list(r, "sebelum");
    r = remove_nth_from_end(r, 2);  // hapus node ke-2 dari belakang (nilai 4)
    print_list(r, "setelah hapus 2nd from end");
    free_list(r);

    // 3. Intersection
    // a: 1 -> 2 -> 3
    //                |
    //                 4 -> 5 -> null   (shared dengan b)
    //                |
    // b:    9 -> 8
    Node<int>* shared = make_list<int>({4, 5});
    Node<int>* a = make_list<int>({1, 2, 3});
    Node<int>* b = make_list<int>({9, 8});
    // sambungkan tail a dan b ke shared
    Node<int>* ta = a; while (ta->next) ta = ta->next;
    ta->next = shared;
    Node<int>* tb = b; while (tb->next) tb = tb->next;
    tb->next = shared;

    Node<int>* inter = get_intersection(a, b);
    std::cout << "intersection: " << (inter ? inter->nilai : -1) << '\n';

    // cleanup: shared hanya boleh di-delete sekali
    ta->next = nullptr;
    tb->next = nullptr;
    free_list(a);
    free_list(b);
    free_list(shared);

    return 0;
}

Output yang Dihasilkan:

text
palindrome {1,2,3,2,1}: true
palindrome {1,2,3,4,5}: false
palindrome {1,2,2,1}   : true
sebelum: 1 -> 2 -> 3 -> 4 -> 5 -> null
setelah hapus 2nd from end: 1 -> 2 -> 3 -> 5 -> null
intersection: 4

Ringkasan Pola dan Trik #

Pola	Trik Kunci	Time	Space
Palindrome	Slow/fast + reverse first half in-place	O(n)	O(1)
Remove nth from end	Dummy + two pointers jarak n+1	O(n)	O(1)
Intersection	Samakan offset panjang + compare pointer	O(n+m)	O(1)

Trik berulang yang muncul di banyak soal linked list:

Dummy node — menyederhanakan kasus hapus/insert head.
Slow/fast pointer — find middle, detect cycle, palindrome.
Two pointers dengan jarak tetap — remove nth, sliding window linked list.
Reverse in-place — manipulasi pointer tanpa alokasi baru.
Pointer equality (bukan nilai) — untuk intersection atau cycle detection.

Ringkasan #

Palindrome check O(1) space memakai slow/fast pointer sambil reverse first half in-place.
Remove nth from end O(n) satu pass dengan two pointers berjarak n+1 dan dummy node.
Intersection point membandingkan pointer (bukan nilai); samakan offset panjang untuk single pass.
Trik berulang: dummy node, slow/fast pointer, two pointers berjarak tetap, reverse in-place.
Kuasai pola-pola ini — banyak soal linked list interview hanyalah variasi dari empat lima trik dasar.