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:
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.
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.

Memuat komentar...