LeetCode Grinding
Algorithms1 menit baca

Pengantar Manipulasi In-Place pada Linked List

Membalik linked list dengan mengubah link-nya sambil tetap menjaga akses ke node yang tersisa.

Untuk membalik linked list, aku bisa mengubah node yang dituju setiap link. Yang perlu dijaga adalah node berikutnya: setelah link ditimpa, aku masih perlu akses ke sisa list.

Linked list secara in place

Pembalikan in place mengubah pointer next yang udah ada dan memakai O(1) extra space. Menyalin value ke list baru juga bisa, tapi cara itu mengalokasikan node pengganti:

javascript
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).

Untuk versi in place, aku menyimpan reference ke node sebelumnya, saat ini, dan berikutnya. Menyimpan reference berikutnya sebelum mengubah link menjaga sisa node tetap bisa diakses.

javascript
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).

Saat memeriksa pembalikan list, aku mengecek urutan assignment itu. Menyimpan current.next setelah menimpanya bakal menghilangkan jalur ke node yang belum diproses.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan