0Pricing
Coding Interview Prep · Pelajaran

Membalik Linked List

Balik linked list tunggal secara iteratif dengan menyusun ulang tiga pointer dan secara rekursif, sambil menelusuri setiap langkah pada diagram bergaya papan tulis.

Membalik Linked List adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Mengapa Pembalikan Daftar Itu Penting

Pembalikan daftar tertaut termasuk pertanyaan wawancara pemrograman yang paling sering diajukan. Hal ini menguji kemampuan Anda untuk memanipulasi penunjuk secara tepat tanpa kehilangan jejak simpul. Variasinya muncul sebagai masalah tersendiri dan sebagai langkah dalam algoritme yang lebih besar, seperti deteksi palindrom, pengurutan ulang daftar, dan pembalikan per kelompok k.

Pendekatan iteratif menggunakan tiga penunjuk: prev, curr, dan next_node. Pendekatan rekursif menyatakan logika yang sama sebagai penelusuran tumpukan pemanggilan. Keduanya mencapai waktu O(n), sedangkan pendekatan iteratif menggunakan ruang O(1).

Pembalikan Iteratif dengan Tiga Penunjuk

Pada setiap langkah pembalikan iteratif: simpan curr.next agar sisa daftar tidak hilang, balikkan curr.next agar menunjuk ke belakang menuju prev, majukan prev ke curr, lalu majukan curr ke penunjuk berikutnya yang telah disimpan. Ketika curr menjadi kosong, perulangan berakhir dan prev menjadi kepala baru.

Jembatan ingatan yang berguna: Simpan, Balik, Majukan, Majukan.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node  = curr.next   # Save
        curr.next  = prev        # Flip
        prev       = curr        # Advance prev
        curr       = next_node   # Advance curr
    return prev  # new head

# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
    print(head.val, end=' ')  # 5 4 3 2 1
    head = head.next

Pelacakan Langkah demi Langkah

Mari kita lacak reverse_list pada 1 -> 2 -> 3. Awalnya prev=None, curr=1. Langkah 1: simpan next=2, balikkan 1.next=None, prev=1, curr=2. Langkah 2: simpan next=3, balikkan 2.next=1, prev=2, curr=3. Langkah 3: simpan next=None, balikkan 3.next=2, prev=3, curr=None. Perulangan berakhir; kembalikan prev=3, yang merupakan kepala baru dari 3 -> 2 -> 1.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_traced(head):
    prev, curr = None, head
    step = 0
    while curr:
        step += 1
        next_node = curr.next
        curr.next = prev
        print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
        prev = curr
        curr = next_node
    return prev

nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val)  # 3

Pembalikan Rekursif

Pendekatan rekursif mengandalkan bahwa reverse_list(head.next) mengembalikan kepala baru dari sufiks yang sudah dibalik. Yang tersisa hanyalah membalikkan penunjuk antara head dan head.next: tetapkan head.next.next = head (arahkan simpul kedua yang lama kembali ke simpul pertama yang lama) dan head.next = None (putuskan tautan maju yang lama). Kepala baru diteruskan kembali dari kasus dasar.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_rec(head):
    # Base case: empty or single node
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)  # reverse suffix
    head.next.next = head   # former second node points back
    head.next = None        # sever forward link
    return new_head

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
    print(head.val, end=' ')  # 4 3 2 1
    head = head.next

Membalik Subdaftar (LeetCode 92)

LeetCode 92 'Membalik Daftar Tertaut II' meminta Anda membalik subdaftar dari posisi kiri ke kanan (berindeks mulai dari 1) dalam satu lintasan. Triknya adalah menemukan simpul sebelum subdaftar tersebut (gunakan kepala semu agar posisi ini selalu valid), lalu lakukan pembalikan dengan tiga penunjuk tepat selama (right - left) langkah, dan terakhir sambungkan kembali segmen yang dibalik ke daftar di sekitarnya.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    pre = dummy
    # Advance pre to node just before position 'left'
    for _ in range(left - 1):
        pre = pre.next
    curr = pre.next
    for _ in range(right - left):
        next_node   = curr.next
        curr.next   = next_node.next
        next_node.next = pre.next
        pre.next    = next_node
    return dummy.next

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
    print(head.val, end=' ')  # 1 4 3 2 5
    head = head.next

Membalik Simpul dalam Kelompok k (LeetCode 25)

LeetCode 25 'Membalik Simpul dalam Kelompok k' membalik setiap kelompok berurutan yang terdiri dari k simpul. Pendekatannya: periksa apakah masih ada k simpul; jika tidak, biarkan simpul-simpul tersebut apa adanya. Balikkan k simpul berikutnya menggunakan metode iteratif, lalu balikkan sisa daftar secara rekursif dan sambungkan hasilnya. Kompleksitas waktunya tetap O(n), dengan kedalaman pemanggilan rekursif O(n/k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    # Check if k nodes are available
    curr, count = head, 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head   # fewer than k nodes left, keep as-is
    # Reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # head is now the tail of the reversed group
    head.next = reverseKGroup(curr, k)
    return prev

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
    print(head.val, end=' ')  # 2 1 4 3 5
    head = head.next

Daftar Tertaut Palindrom

LeetCode 234 'Daftar Tertaut Palindrom': periksa apakah suatu daftar tertaut merupakan palindrom dalam waktu O(n) dan ruang O(1). Strateginya: temukan titik tengah dengan penunjuk lambat-cepat, balikkan paruh kedua di tempat, bandingkan kedua paruh simpul demi simpul, lalu pulihkan daftar jika diperlukan. Ini menggabungkan pencarian titik tengah dan pembalikan—dua keterampilan dasar.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find mid
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

def build(arr):
    d = ListNode(0)
    c = d
    for v in arr:
        c.next = ListNode(v)
        c = c.next
    return d.next

print(isPalindrome(build([1,2,2,1])))  # True
print(isPalindrome(build([1,2,3])))    # False

Perbandingan Iteratif dan Rekursif

Pembalikan iteratif menggunakan ruang O(1) dan umumnya lebih disarankan. Pembalikan rekursif menggunakan ruang tumpukan O(n) karena kedalaman pemanggilan, yang dapat menyebabkan luapan tumpukan untuk daftar yang sangat panjang (batas bawaan Python adalah sekitar 1000 tingkat rekursi).

Dalam wawancara, implementasikan versi iteratif terlebih dahulu untuk menunjukkan pemahaman tentang batasan ruang, lalu sebutkan versi rekursif sebagai alternatif yang lebih bersih jika panjang daftar dibatasi.

import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint

# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)

Kesalahan Umum dalam Pembalikan

Tiga kesalahan mencakup hampir semua bug pembalikan. Pertama, tidak menyimpan next sebelum menimpanya: curr.next = prev menghancurkan referensi ke arah depan jika next_node belum disimpan. Kedua, tidak mengembalikan prev: di akhir perulangan, curr adalah None, sedangkan prev adalah kepala baru. Ketiga, kasus dasar rekursif yang salah: melupakan not head.next berarti daftar dengan satu simpul tidak ditangani dan menyebabkan AttributeError.

# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next   # BUG if omitted: lose rest of list
        curr.next = prev
        prev      = curr
        curr      = next_node
    return prev               # BUG if you return curr: it is None

nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
    print(h.val, end=' ')  # 3 2 1
    h = h.next

Susun Ulang Daftar (LeetCode 143)

LeetCode 143 'Susun Ulang Daftar' menyusun ulang L0 → L1 → L2 → ... → Ln menjadi L0 → Ln → L1 → Ln-1 → L2 → Ln-2 dalam waktu O(n) dan ruang O(1). Solusinya menggabungkan tiga langkah: temukan titik tengah, balikkan paruh kedua, lalu selang-selingkan kedua paruh. Menguasai pembalikan membuat soal yang tampak rumit ini menjadi kombinasi sederhana dari alat-alat yang sudah dikenal.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    # Find mid
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Interleave
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
    print(h.val, end=' ')  # 1 4 2 3
    h = h.next

Ringkasan: Pembalikan Adalah Blok Penyusun

Pembalikan daftar tertaut jarang menjadi tujuan akhir—pembalikan adalah blok penyusun. Deteksi palindrom, pembalikan kelompok k, penyusunan ulang daftar, dan pembalikan antara posisi tertentu semuanya mengandalkan pola iteratif tiga penunjuk yang sama. Setelah pola ini menjadi otomatis, Anda dapat memusatkan kapasitas berpikir pada struktur soal tingkat lebih tinggi.

Selalu latih pembalikan sampai Anda dapat menuliskannya dari ingatan dalam waktu kurang dari dua menit; pembalikan akan muncul dalam bentuk tertentu di hampir setiap sesi wawancara tentang daftar tertaut.

Uji Cepat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini Anda mempelajari: pola iteratif Simpan-Balikkan-Majukan-Majukan membalik daftar dalam waktu O(n) dan ruang O(1), pendekatan rekursif menganggap sufiks sudah dibalik dan hanya memperbaiki tautan terakhir, serta pembalikan merupakan sublangkah inti dalam deteksi palindrom, penyusunan ulang daftar, dan pembalikan kelompok k. Berikutnya kita akan membahas deteksi siklus dengan algoritma Floyd.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Membalik Linked List” gratis?

Ya — teks lengkap “Membalik Linked List” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Membalik Linked List”?

Balik linked list tunggal secara iteratif dengan menyusun ulang tiga pointer dan secara rekursif, sambil menelusuri setiap langkah pada diagram bergaya papan tulis. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.

Berapa lama pelajaran “Membalik Linked List” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Kelas Node dan Pembuatan List
  2. Membalik Linked List
  3. Deteksi Siklus dengan Algoritma Floyd
  4. Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir
← Kembali ke Coding Interview Prep