Solusi Leetcode - Reverse Linked List

Membalik linked list adalah skill dasar yang sering muncul di coding interview. Solusi pertama saya bikin list baru, yang memang jalan tapi pakai extra memory O(n). Lalu saya belajar teknik in place yang cuma pakai space O(1) dengan mengubah ke mana node-node itu menunjuk.

Node yang udah ada sebenarnya udah cukup. Algoritmanya mengubah pointer next mereka dan menyimpan referensi ke node sebelumnya, node saat ini, dan node berikutnya.

Memahami Soalnya

Diberikan head dari sebuah singly linked list, balik list itu lalu return head yang baru. Solusinya harus pakai extra space O(1). Solusinya nggak boleh mengalokasikan node pengganti atau struktur data yang ikut membesar seiring panjang list.

Pendekatan Pertama Saya

Solusi awal saya mengumpulkan semua nilai ke dalam array, lalu menaruh setiap nilai di depan list baru. Nilai-nilainya harus dibaca sesuai urutan aslinya supaya cara ini bisa membalik list. Sediakan constructor ListNode(value, next) kalau mau menjalankan versi ini di luar platform soalnya.

function reverseLinkedListNaive(head) {
  const values = [];
  let current = head;

  // Collect values
  while (current) {
    values.push(current.val);
    current = current.next;
  }

  // Build new list in reverse
  let newHead = null;
  for (let i = 0; i < values.length; i++) {
    newHead = new ListNode(values[i], newHead);
  }

  return newHead;
}

Versi ini butuh extra space O(n) untuk array-nya dan bikin node baru. Membalik link yang udah ada menghilangkan kedua alokasi itu.

Pendekatan In Place

Saya menyimpan tiga referensi supaya setiap perubahan pointer tetap menjaga akses ke node-node yang tersisa:

• prev: Node sebelumnya (supaya kita bisa mengarahkan current ke node ini)
• current: Node yang sedang kita proses
• next: Node berikutnya (supaya kita nggak kehilangan sisa list-nya)

Algoritmanya jalan dengan menelusuri list sambil membalik setiap link yang dilewati. Kita simpan node berikutnya sebelum membalik link, lalu majukan ketiga pointer.

Pembalikan in place

function reverseLinkedList(head) {
  let prev = null; // Previous node (starts as null - new tail)
  let current = head; // Current node we're processing

  while (current !== null) {
    // Save next node before we lose it
    let next = current.next;

    // Reverse the link: point current to previous
    current.next = prev;

    // Move both pointers forward
    prev = current;
    current = next;
  }

  // prev is now the new head
  return prev;
}

Perubahan pointer

Untuk 1 → 2 → 3 → 4 → null, pointer-nya bergerak seperti ini:

Kondisi awal: 1 → 2 → 3 → 4 → null

• prev = null, current = 1

Langkah 1:

• Simpan next = 2
• Balik link: 1 → null
• Maju: prev = 1, current = 2
• Kondisi: null ← 1 2 → 3 → 4 → null

Langkah 2:

• Simpan next = 3
• Balik link: 2 → 1
• Maju: prev = 2, current = 3
• Kondisi: null ← 1 ← 2 3 → 4 → null

Langkah 3:

• Simpan next = 4
• Balik link: 3 → 2
• Maju: prev = 3, current = 4
• Kondisi: null ← 1 ← 2 ← 3 4 → null

Langkah 4:

• Simpan next = null
• Balik link: 4 → 3
• Maju: prev = 4, current = null
• Kondisi: null ← 1 ← 2 ← 3 ← 4

Hasil: 4 → 3 → 2 → 1 → null

Kenapa Ini Berhasil

Algoritmanya bekerja dengan membalik setiap link secara sistematis:

1. Simpan node berikutnya: Begitu link-nya dibalik, kita kehilangan akses ke sisa list
2. Balik link saat ini: Arahkan current.next ke prev
3. Majukan kedua pointer: prev jadi current, current jadi next
4. Ulangi: Lanjutkan sampai node current bernilai null

Waktu loop selesai, prev menunjuk ke node yang tadinya node terakhir, yang sekarang jadi head baru.

Analisis Kompleksitas

Time Complexity: O(n)

• Kita mengunjungi setiap node tepat satu kali
• Setiap operasi (menyimpan next, membalik link, memajukan pointer) bernilai O(1)

Space Complexity: O(1)

• Cuma pakai tiga variabel pointer (prev, current, next)
• Nggak ada struktur data tambahan
• Nggak ada node baru yang dibuat

Jebakan Umum

Waktu mengimplementasikan ini, hati-hati dengan:

1. Kehilangan sisa list: Selalu simpan next sebelum membalik link
2. Me-return node yang salah: Ingat bahwa prev adalah head baru setelah loop
3. Edge case: Tangani list kosong (head === null) dan list dengan satu node
4. Null pointer error: Pastikan mengecek current !== null di kondisi loop

Ringkasan pembalikan

• Manipulasi in place pakai extra space O(1)
• Lacak prev, current, dan next, lalu simpan next sebelum membalik link
• Pola melacak beberapa pointer sekaligus berlaku di banyak soal linked list

Belajar manipulasi in place mengubah cara saya memandang linked list. Sekarang saya cari cara untuk menyusun ulang node yang udah ada sebelum bikin struktur baru. Teknik ini berguna di soal linked list lainnya.