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.
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 prosesnext: 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
- Simpan node berikutnya: Begitu link-nya dibalik, kita kehilangan akses ke sisa list
- Balik link saat ini: Arahkan current.next ke prev
- Majukan kedua pointer: prev jadi current, current jadi next
- 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
- Kehilangan sisa list: Selalu simpan
nextsebelum membalik link - Me-return node yang salah: Ingat bahwa
prevadalah head baru setelah loop - Edge case: Tangani list kosong (head === null) dan list dengan satu node
- Null pointer error: Pastikan mengecek
current !== nulldi kondisi loop

Memuat komentar...