Linked list bukan sekadar wadah — banyak algoritma klasik memanfaatkan sifat unik pointer untuk solusi elegan. Membalik list (reverse), menemukan node tengah, mendeteksi cycle, dan menggabungkan dua list terurut adalah operasi fundamental yang muncul di soal interview maupun implementasi nyata. Pada Chapter ini kita akan membedah empat operasi ini dengan pendekatan pointer-based, membandingkan versi iteratif dan rekursif, serta menjelaskan algoritma Floyd untuk deteksi cycle. Setiap algoritma disertai analisis kompleksitas time dan space.

Reverse Linked List (Iteratif) #

Aturan #

Diberikan head linked list, balikkan urutan node sehingga head lama menjadi tail dan sebaliknya.

Mekanisme: Tiga Pointer Dancing #

Kita menjaga tiga pointer selama iterasi:

  1. prev — node sebelum cur (di awal nullptr).
  2. cur — node saat ini.
  3. nx — node berikutnya (disimpan sebelum cur->next diubah).

Pada tiap langkah, cur->next diputar dari nx ke prev, lalu ketiga pointer bergeser maju.

Kode: Reverse Iteratif #

cpp 
template <typename T>
Node<T>* reverse_iterative(Node<T>* head) {
    Node<T>* prev = nullptr;
    Node<T>* cur = head;
    while (cur != nullptr) {
        Node<T>* nx = cur->next;  // simpan next sebelum diputar
        cur->next = prev;          // putar: cur menunjuk ke belakang
        prev = cur;                 // majukan prev
        cur = nx;                   // majukan cur
    }
    return prev;  // head baru
}

Line-by-line #

  1. Node<T>* nx = cur->next;: wajib disimpan sebelum cur->next diubah. Tanpa ini, kita kehilangan akses ke node berikutnya.
  2. cur->next = prev;: inti reverse — pointer next diputar ke arah belakang. Pada iterasi pertama, head lama menunjuk ke nullptr (sebagai tail baru).
  3. prev = cur; cur = nx;: kedua pointer maju satu langkah. prev menjadi cur lama, cur menjadi nx (yang sudah disimpan).
  4. return prev;: setelah loop selesai, cur == nullptr dan prev menunjuk ke node terakhir (head baru). Bila list kosong, prev tetap nullptr.

Kompleksitas: O(n) waktu, O(1) memori tambahan. Hanya tiga pointer lokal — tanpa alokasi baru.

Reverse Linked List (Rekursif) #

Mekanisme: Recursion Until Tail, Then Reverse Pointers #

Pendekatan rekursif menulusuri sampai tail, lalu pada saat balik (unwinding), setiap node memutar pointer next dari node setelahnya kembali ke dirinya.

cpp 
template <typename T>
Node<T>* reverse_recursive(Node<T>* head) {
    if (head == nullptr || head->next == nullptr) return head;
    Node<T>* new_head = reverse_recursive(head->next);
    head->next->next = head;  // node setelah head kini menunjuk balik
    head->next = nullptr;     // putuskan rantai lama
    return new_head;
}

Line-by-line #

  1. if (head == nullptr || head->next == nullptr) return head;: kasus dasar — list kosong atau satu node adalah list yang sudah terbalik. new_head adalah tail dari list asli.
  2. head->next->next = head;: trik kuncinya. Karena head->next sudah menjadi node terakhir dari list terbalik (yang di-return sebagai new_head adalah ujung), head->next->next = head memutar node setelah head untuk menunjuk balik ke head.
  3. head->next = nullptr;: head menjadi tail baru — next-nya harus nullptr.

Kompleksitas: O(n) waktu, O(n) memori stack. Setiap panggilan rekursif menambah frame stack — untuk list sangat panjang, dapat menyebabkan stack overflow.

Find Middle: Slow-Fast Pointer #

Aturan #

Temukan node tengah linked list dalam satu pass tanpa menghitung panjang terlebih dahulu.

Mekanisme: Fast Bergerak Dua Kali Lebih Cepat #

Pointer slow bergerak satu langkah per iterasi, fast dua langkah. Saat fast mencapai akhir, slow berada di tengah.

Kode: Find Middle #

cpp 
template <typename T>
Node<T>* find_middle(Node<T>* head) {
    Node<T>* slow = head;
    Node<T>* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Line-by-line #

  1. slow = slow->next;: maju satu langkah.
  2. fast = fast->next->next;: maju dua langkah. Bila panjang ganjil, fast berakhir di node terakhir (bukan nullptr), dan slow berada di tengah persis.
  3. Kondisi fast != nullptr && fast->next != nullptr: berhenti saat fast mencapai akhir atau satu node sebelum akhir. Untuk panjang genap, slow berakhir di node kedua dari pasangan tengah.

Kompleksitas: O(n) waktu, O(1) memori. Satu pass tanpa pre-compute panjang.

Detect Cycle: Algoritma Floyd #

Aturan #

Tentukan apakah linked list memiliki cycle (node yang next-nya menunjuk ke node sebelumnya dalam list, membentuk loop).

Mekanisme: Tortoise dan Hare #

Pointer slow (kura-kura) bergerak satu langkah, fast (kelinci) dua langkah. Bila ada cycle, fast akan mengejar slow dari belakang dan keduanya bertemu. Bila tidak ada cycle, fast mencapai nullptr duluan.

Mengapa dijamin bertemu? Bila ada cycle, jarak fast dan slow dalam cycle berkurang 1 setiap iterasi (fast mengejar 2 langkah, slow melarikan 1 langkah). Pada suatu saat, jarak menjadi 0 — mereka bertemu.

cpp 
template <typename T>
bool has_cycle(Node<T>* head) {
    Node<T>* slow = head;
    Node<T>* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
  1. if (slow == fast) return true;: pengecekan setelah kedua pointer bergerak. Bila list punya cycle, keduanya akan sama-sama masuk ke cycle dan akhirnya bertemu di dalamnya.
  2. return false;: bila fast mencapai nullptr atau fast->next == nullptr, berarti tidak ada cycle — list berakhir normal.

Kompleksitas: O(n) waktu, O(1) memori. Jauh lebih efisien dibanding hash set O(n) space.

Merge Two Sorted Lists (Iteratif) #

Aturan #

Diberikan dua linked list terurut menaik, gabungkan menjadi satu list terurut tanpa mengalokasikan node baru.

Mekanisme: Dummy Head + Tail Pointer #

Gunakan node dummy sebagai anchor agar tidak perlu kasus khusus untuk node pertama. Tail pointer menunjuk ke node terakhir dari hasil yang sedang dibangun.

cpp 
template <typename T>
Node<T>* merge_sorted(Node<T>* a, Node<T>* b) {
    Node<T> dummy(T{});
    Node<T>* tail = &dummy;
    while (a != nullptr && b != nullptr) {
        if (a->nilai <= b->nilai) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != nullptr) ? a : b;
    return dummy.next;
}

Line-by-line #

  1. Node<T> dummy(T{});: node dummy dengan nilai default. Tidak pernah dilihat pengguna; hanya untuk menyederhanakan logika insert pertama.
  2. tail->next = a; atau b: sambungkan node yang lebih kecil ke akhir hasil.
  3. tail = tail->next;: majukan tail ke node yang baru disambung.
  4. tail->next = (a != nullptr) ? a : b;: bila salah satu list habis, sambungkan seluruh sisa list lainnya. Tidak perlu loop elemen-per-elemen.
  5. return dummy.next;: dummy.next adalah head asli dari hasil (skip dummy).

Kompleksitas: O(n + m) waktu, O(1) memori tambahan. Node digunakan ulang — tidak ada alokasi baru.

Kode Gabungan Semua Operasi #

cpp 
#include <iostream>

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

// Reverse iteratif: O(n) time, O(1) space
template <typename T>
Node<T>* reverse_iterative(Node<T>* head) {
    Node<T>* prev = nullptr;
    Node<T>* cur = head;
    while (cur != nullptr) {
        Node<T>* nx = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nx;
    }
    return prev;  // head baru
}

// Reverse rekursif: O(n) time, O(n) stack
template <typename T>
Node<T>* reverse_recursive(Node<T>* head) {
    if (head == nullptr || head->next == nullptr) return head;
    Node<T>* new_head = reverse_recursive(head->next);
    head->next->next = head;  // node setelah head kini menunjuk balik
    head->next = nullptr;     // putuskan rantai lama
    return new_head;
}

// Find middle: slow/fast pointer
template <typename T>
Node<T>* find_middle(Node<T>* head) {
    Node<T>* slow = head;
    Node<T>* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // untuk panjang ganjil = tengah, genap = node kedua dari tengah
}

// Detect cycle: Floyd's tortoise & hare
template <typename T>
bool has_cycle(Node<T>* head) {
    Node<T>* slow = head;
    Node<T>* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Merge two sorted lists (iteratif): O(n+m)
template <typename T>
Node<T>* merge_sorted(Node<T>* a, Node<T>* b) {
    Node<T> dummy(T{});
    Node<T>* tail = &dummy;
    while (a != nullptr && b != nullptr) {
        if (a->nilai <= b->nilai) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != nullptr) ? a : b;
    return dummy.next;
}

template <typename T>
void print_list(Node<T>* head) {
    for (Node<T>* c = head; c != nullptr; c = c->next) {
        std::cout << c->nilai << (c->next ? " -> " : " -> null\n");
    }
}

template <typename T>
Node<T>* make_list(const std::initializer_list<T>& vals) {
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;
    for (const T& v : vals) {
        Node<T>* n = new Node<T>(v);
        if (head == nullptr) head = tail = n;
        else { tail->next = n; tail = n; }
    }
    return head;
}

template <typename T>
void free_list(Node<T>* head) {
    while (head != nullptr) {
        Node<T>* nx = head->next;
        delete head;
        head = nx;
    }
}

int main() {
    // Reverse iteratif
    Node<int>* a = make_list<int>({1, 2, 3, 4, 5});
    std::cout << "awal     : "; print_list(a);
    a = reverse_iterative(a);
    std::cout << "reverse  : "; print_list(a);
    a = reverse_recursive(a);
    std::cout << "reverse 2: "; print_list(a);

    // Find middle
    Node<int>* mid = find_middle(a);
    std::cout << "middle   : " << (mid ? mid->nilai : -1) << '\n';

    // Detect cycle
    std::cout << "has_cycle(a): " << std::boolalpha << has_cycle(a) << '\n';
    // buat cycle: node terakhir a menunjuk ke node kedua
    Node<int>* second = a->next;
    Node<int>* cur = a;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = second;  // buat cycle
    std::cout << "has_cycle(a) after loop: " << has_cycle(a) << '\n';
    cur->next = nullptr;  // putuskan cycle sebelum free

    free_list(a);

    // Merge two sorted
    Node<int>* x = make_list<int>({1, 3, 5, 7});
    Node<int>* y = make_list<int>({2, 4, 6, 8, 10});
    Node<int>* merged = merge_sorted(x, y);
    std::cout << "merged   : "; print_list(merged);
    free_list(merged);

    return 0;
}

Output yang Dihasilkan:

text 
awal     : 1 -> 2 -> 3 -> 4 -> 5 -> null
reverse  : 5 -> 4 -> 3 -> 2 -> 1 -> null
reverse 2: 1 -> 2 -> 3 -> 4 -> 5 -> null
middle   : 3
has_cycle(a): false
has_cycle(a) after loop: true
merged   : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 10 -> null

Tabel Ringkas Kompleksitas #

OperasiTimeSpace (aux)Catatan
Reverse iteratifO(n)O(1)Tiga pointer
Reverse rekursifO(n)O(n)Stack frame per node
Find middleO(n)O(1)Slow/fast pointer
Detect cycle (Floyd)O(n)O(1)Tortoise & hare
Merge sortedO(n+m)O(1)Dummy head trick

Ringkasan #

  • Reverse iteratif memakai tiga pointer (prev, cur, nx) dengan O(1) space; rekursif lebih elegan tetapi O(n) stack.
  • Find middle memanfaatkan slow/fast pointer — satu pass, O(1) space.
  • Algoritma Floyd mendeteksi cycle O(n) time O(1) space; ekstensi dapat menemukan titik mulai cycle.
  • Merge sorted memakai dummy head untuk menyederhanakan kasus khusus; tail pointer memungkinkan append O(1).
  • Pola pointer-based (slow/fast, dummy head, three-pointer reverse) muncul berulang di banyak algoritma linked list — kuasai pola ini dan banyak soal lain jadi terlihat familiar.