Pengantar Manipulasi In-Place pada Linked List

Membalik linked list nggak butuh list kedua. Node-nya bisa tetap di tempatnya, sementara link-nya yang berubah. Teknik in place ini membuka cara berpikir yang beda tentang linked list buat saya.

Linked list secara in place

Modifikasi in place memakai extra space O(1) di luar input. Untuk linked list, artinya meng-update pointer next tanpa mengalokasikan node pengganti. Waktu pertama kali saya mencoba membalik linked list, saya menyalin nilainya lalu membangun list baru:

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

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

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

  return newHead;
}

Loop-nya membaca nilai sesuai urutan aslinya dan menyisipkan setiap node baru di head. Ini membalik list-nya. Array values dan node pengganti memakai extra space O(n). Di luar platform soalnya, contoh ini butuh constructor ListNode(value, next).

Saya nggak butuh node baru. Saya menyimpan reference ke node sebelumnya, node saat ini, dan node berikutnya. Reference ini menjaga akses ke list waktu sebuah link berubah.

Implementasi in place-nya:

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

  while (current !== null) {
    let next = current.next; // Save next node
    current.next = prev; // Reverse the link!
    prev = current; // Move prev forward
    current = next; // Move current forward
  }

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

Setiap putaran loop menyimpan node berikutnya sebelum mengubah current.next. Lalu loop meng-set current.next ke prev dan memajukan prev ke node saat ini. Loop berlanjut dari node berikutnya yang udah disimpan tadi. Begitu current bernilai null, prev menunjuk ke head yang baru.

Kompleksitas dan penerapannya

List-nya ditelusuri sekali, jadi time complexity-nya O(n). Algoritmanya menyimpan tiga reference dan memakai extra space O(1).

Saya jadi tahu kalau cara menyambung ulang link yang sama juga muncul di:

• Manajemen file system: Menyusun ulang struktur direktori
• Manajemen memori: Mengoptimalkan susunan blok memori
• Optimasi compiler: Menyusun ulang representasi kode

Manipulasi in place mengubah hubungan antar node, bukan menyalin data. Melacak node sebelumnya, saat ini, dan berikutnya udah cukup untuk membalik list dengan waktu linear dan extra space konstan. Mempelajari ini mengubah cara saya mendekati soal linked list: sekarang saya mencari cara aman untuk menulis ulang link yang udah ada lebih dulu.