Soal-soal list klasik

Tiga soal muncul berulang-ulang dalam latihan dan wawancara teknis, yaitu membalik arah list, mendeteksi siklus, dan menggabungkan dua list terurut. Ketiganya tidak memerlukan struktur baru, hanya disiplin pointer yang sudah dilatih pada topik-topik modul ini. Setiap teknik dijelaskan dengan diagramnya, diimplementasikan dalam satu berkas Python, pembalikan dicerminkan pada Java, dan halaman ditutup dengan daftar soal untuk dipraktikkan.

Membalik arah list dengan tiga pointer#

Membalik list berarti mengubah arah setiap tautan, dan pekerjaan itu dilakukan satu node demi satu node dengan tiga pointer. Pointer prev menyimpan bagian yang sudah dibalik, curr berdiri di node yang sedang diproses, dan lanjut menjaga sisa list agar tidak hilang ketika tautan lama diputus. Nilai prev dimulai dari null karena bagian yang sudah dibalik di awal memang kosong, dan perulangan berhenti ketika sisa list habis.

Diagram berikut memotret satu langkah perulangan saat curr berada di node 2. Sisa list disimpan lebih dulu di lanjut, tautan lama menuju node 3 diputus, dan tautan baru menunjuk ke node 1 yang sudah dibalik.

Invarian perulangannya mudah diperiksa, yaitu prev selalu menjadi head dari bagian yang sudah dibalik dan curr selalu menjadi head dari sisa list. Setiap putaran memindahkan satu node dari sisa ke hasil, sehingga waktu berjalan $O(n)$ tanpa memori tambahan yang berarti. Setelah perulangan selesai, prev menjadi head baru dan list lama kini dibaca dari ujung belakangnya.

Deteksi siklus dengan Floyd#

Siklus terjadi ketika tautan sebuah node menunjuk ke node yang ada di belakangnya, sehingga penelusuran biasa berputar selamanya. Algoritma Floyd, yakni deteksi siklus dengan dua pointer berkecepatan berbeda, menempatkan pointer lambat yang melangkah satu dan pointer cepat yang melangkah dua. Pola cepat dan lambat seperti ini sudah dikenal dari modul two pointer, dan pada linked list polanya bekerja tanpa indeks sama sekali.

Di dalam siklus, kedua pointer tidak mungkin saling melewati begitu saja. Jarak keduanya berkurang satu setiap putaran, karena yang cepat bergerak dua langkah sementara yang lambat satu langkah. Penyusutan satu demi satu itu pasti mencapai nol, sehingga pointer cepat mendarat tepat pada posisi pointer lambat, bukan melompatinya. Pertemuan itu terjadi tepat di dalam siklus, sedangkan pada list tanpa siklus pointer cepat lebih dulu mencapai null.

Menggabungkan dua list terurut#

Menggabungkan dua list yang masing-masing sudah terurut berarti memindahkan node bernilai lebih kecil satu per satu ke hasil. Dummy head, yakni node pembuka tanpa data yang tidak dihitung sebagai hasil, memegang peran penting di sini karena head hasil belum diketahui sebelum perbandingan pertama. Tanpa dummy, hasil pertama harus ditentukan dengan percabangan tersendiri, dan dengan dummy cukup mengembalikan dummy.next di akhir.

Perulangan berhenti ketika salah satu list habis, lalu sisa list yang lain disambungkan apa adanya karena sisa itu sudah terurut. Karena tidak ada node baru yang dibuat, waktu berjalan $O(n + m)$ untuk dua list berukuran n dan m tanpa memori tambahan yang berarti. Trik yang sama persis dipakai keluarga soal gabungan k list, hanya saja pemilih node terbaiknya diganti struktur heap, yakni antrian prioritas berbentuk pohon.

Perbandingan memakai <= agar node dari list pertama mendahului node yang nilainya sama, dan pilihan itu menjaga urutan relatif kedua list. Bila nilai 3 muncul di kedua list, node milik list pertama keluar lebih dulu. Sifat stabil seperti ini menjadi penting ketika penggabungan menjadi bagian dari merge sort, yakni algoritma pengurutan yang menggabungkan dua potongan terurut.

Implementasi ketiganya dalam satu berkas#

Berkas berikut merangkum ketiga teknik di atas beserta dua fungsi bantu, yaitu buat_list yang merakit list dari deretan nilai dan render yang mencetak nilai node tanpa alamat memori. Demo utamanya membalik list 1 sampai 4, membangun siklus pada list lain untuk diuji Floyd, lalu menggabungkan dua list terurut 1, 3, 5 dan 2, 4, 6. Jalankan kodenya, lalu cocokkan setiap baris keluaran dengan teknik yang menyebabkannya.

"""Tiga soal klasik linked list: pembalikan, deteksi siklus, dan penggabungan."""


class Node:
    """Satu node menyimpan data dan tautan next menuju node sesudahnya."""

    def __init__(self, data):
        self.data = data
        self.next = None


def buat_list(nilai):
    """Bangun list dari deretan nilai, lalu kembalikan head-nya."""
    head = None
    for v in reversed(nilai):
        node = Node(v)
        node.next = head
        head = node
    return head


def render(head):
    """Tampilkan rantai sebagai teks berisi nilai, bukan alamat memori."""
    bagian = []
    kini = head
    while kini is not None:
        bagian.append(str(kini.data))
        kini = kini.next
    if not bagian:
        return "None"
    return " -> ".join(bagian) + " -> None"


def balik(head):
    """Balik arah list dengan tiga pointer prev, curr, dan lanjut."""
    prev = None
    curr = head
    while curr is not None:
        lanjut = curr.next      # simpan sisa list sebelum tautannya diputus
        curr.next = prev        # balik satu tautan menunjuk ke belakang
        prev = curr             # prev merangkak maju ke node yang sudah dibalik
        curr = lanjut           # curr maju ke sisa list yang belum dibalik
    return prev


def punya_siklus(head):
    """Deteksi siklus dengan Floyd: lambat satu langkah, cepat dua langkah."""
    lambat = cepat = head
    while cepat is not None and cepat.next is not None:
        lambat = lambat.next
        cepat = cepat.next.next
        if lambat is cepat:
            return True
    return False


def gabung_terurut(a, b):
    """Gabungkan dua list terurut menjadi satu, memakai dummy head."""
    dummy = Node(0)             # sentinel yang tidak termasuk hasil
    ekor = dummy
    while a is not None and b is not None:
        if a.data <= b.data:
            ekor.next = a
            a = a.next
        else:
            ekor.next = b
            b = b.next
        ekor = ekor.next
    ekor.next = a if a is not None else b   # sisa salah satu list disambung
    return dummy.next


if __name__ == "__main__":
    a = buat_list([1, 2, 3, 4])
    print("list awal      :", render(a))
    print("dibalik        :", render(balik(a)))

    b = buat_list([1, 2, 3, 4])
    b.next.next.next.next = b.next     # siklus: node 4 menunjuk node 2
    print("punya siklus   :", punya_siklus(b))
    c = buat_list([5, 6, 7])
    print("tanpa siklus   :", punya_siklus(c))

    d = buat_list([1, 3, 5])
    e = buat_list([2, 4, 6])
    print("gabung terurut :", render(gabung_terurut(d, e)))

list awal      : 1 -> 2 -> 3 -> 4 -> None
dibalik        : 4 -> 3 -> 2 -> 1 -> None
punya siklus   : True
tanpa siklus   : False
gabung terurut : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

Baris b.next.next.next.next = b.next membangun siklus dengan menunjuk node terakhir ke node kedua, dan setiap percobaan seperti itu harus disertai pertanyaan apakah list masih berakhir di null. Nilai punya_siklus bernilai True hanya butuh beberapa putaran untuk list empat node, sedangkan nilai False pada list biasa menunjukkan penelusuran berakhir di null. Penggabungan menghasilkan urutan 1 sampai 6 dengan memakai node asli dari kedua list, bukan salinannya.

Fungsi render sengaja mencetak nilai dan bukan hasil repr node, karena repr default memuat alamat memori yang berubah pada setiap eksekusi. Keluaran yang stabil seperti itu bisa dibandingkan baris demi baris tanpa kejutan. Berkas ini juga menjadi templat pengerjaan soal serupa, karena kerangkanya, yaitu fungsi bantu, teknik, dan demo, tinggal disalin lalu diganti isinya.

Demo pembalikan pada Java#

Pembalikan tiga pointer dipindahkan ke Java hampir tanpa perubahan, hanya tanda tipe dan tanda kurung kurawal yang bertambah. Metode statis balik menerima head lama dan mengembalikan head baru, sedangkan render merakit teks dengan StringBuilder. Program dijalankan langsung dengan java BalikList.java tanpa tahap kompilasi manual.

public class BalikList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    static Node balik(Node head) {
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node lanjut = curr.next;   // simpan sisa list sebelum tautan diputus
            curr.next = prev;          // balik satu tautan menunjuk ke belakang
            prev = curr;
            curr = lanjut;
        }
        return prev;
    }

    static String render(Node head) {
        StringBuilder teks = new StringBuilder();
        Node kini = head;
        while (kini != null) {
            teks.append(kini.data);
            teks.append(" -> ");
            kini = kini.next;
        }
        teks.append("null");
        return teks.toString();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        System.out.println("list awal      : " + render(head));
        head = balik(head);
        System.out.println("dibalik        : " + render(head));
    }
}

list awal      : 1 -> 2 -> 3 -> 4 -> null
dibalik        : 4 -> 3 -> 2 -> 1 -> null

Keluarannya identik dengan versi Python karena mekanismenya memang sama. Mencoba teknik yang sama pada dua bahasa dengan pengelolaan memori yang berbeda memperlihatkan bahwa kebenaran algoritma terletak pada urutan penataan ulang tautannya, bukan pada sintaks. Tiga pointer itu, yaitu prev, curr, dan lanjut, menjadi pola siap pakai untuk banyak soal linked list.

Kelas Node pada demo bersifat statis dengan data bertipe int, dan rantainya dibangun manual lewat head.next.next.next. Rantai manual semacam itu hanya untuk demo pendek, sedangkan list panjang dirakit dengan perulangan yang menambah node satu per satu. Setelah balik mengembalikan head baru, variabel head ditimpa dengan hasilnya agar pencetakan berikutnya membaca arah yang sudah dibalik.

Soal untuk dipraktikkan#

Daftar berikut memetakan soal-soal dari judge daring, yakni layanan penilai kode otomatis, ke tiga teknik yang baru dipraktikkan.

1. Soal Reverse Linked List adalah pembalikan tiga pointer persis seperti bagian pertama halaman ini.
2. Soal Middle of the Linked List melatih pointer cepat dan lambat untuk menemukan node tengah tanpa menghitung panjang list.
3. Soal Linked List Cycle adalah deteksi siklus dengan Floyd pada bentuknya yang paling murni.
4. Soal Linked List Cycle II melanjutkan Floyd untuk menemukan titik awal siklus setelah pertemuan terdeteksi.
5. Soal Merge Two Sorted Lists adalah penggabungan dua list terurut dengan dummy head yang sudah dipraktikkan di atas.
6. Soal Remove Nth Node From End of List menggabungkan dummy head dengan dua pointer yang berjarak n langkah.
7. Soal Add Two Numbers menelusuri dua list paralel sambil merawat carry, yakni simpanan penjumlahan satu digit, dan membangun node hasil.
8. Soal Reorder List memadukan pencarian tengah, pembalikan, dan penyambungan dalam satu soal.

Ringkasan#

• Pembalikan list bergerak dengan tiga pointer prev, curr, dan lanjut, berbiaya $O(n)$ waktu dan $O(1)$ ruang.
• Floyd mendeteksi siklus dengan dua kecepatan yang jaraknya menyusut satu langkah per putaran hingga bertemu.
• Penggabungan dua list terurut memakai dummy head dan selesai dalam $O(n + m)$ tanpa membuat node baru.
• Delapan soal pada bagian praktik memetakan langsung ke tiga teknik ini.

Referensi#

• Cycle detection — Wikipedia — penjelasan algoritma Floyd beserta alasan kedua pointer pasti bertemu.
• Linked list — Wikipedia — kumpulan operasi klasik pada linked list beserta biayanya.
• VisuAlgo — visualisasi pembalikan dan penggabungan list langkah demi langkah.