LeetCode Grinding
Algorithms3 menit baca

Solusi Leetcode - Reverse Linked List

Membandingkan cara membangun ulang linked list dengan membalik link yang udah ada, pakai extra space yang konstan.

Di artikel ini 8 bagian

Aku membalik linked list dengan mengubah link-nya, satu node setiap langkah. Sebelum menimpa link, aku menyimpan node berikutnya supaya sisa list tetap bisa diakses.

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.

Membuat list pengganti

Versi ini mengumpulkan value ke array, lalu menambahkan setiap value ke depan list baru. Membaca value dalam urutan aslinya menghasilkan urutan terbalik. Sediakan constructor ListNode(value, next) untuk menjalankannya di luar platform soal.

javascript
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

Aku 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

javascript
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

  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

  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

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan