Melaksanakan fungsi untuk membalikkan senarai yang dipautkan.

Melaksanakan fungsi untuk membalikkan senarai yang dipautkan.

Untuk melaksanakan fungsi yang membalikkan senarai yang dipautkan, kami akan menggunakan pendekatan berulang mudah di Python. Inilah cara kita dapat melakukannya:

 <code class="python">class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseLinkedList(head): # Initialize pointers prev = None current = head # Traverse the list while current is not None: # Store the next node next_node = current.next # Reverse the link current.next = prev # Move pointers one position ahead prev = current current = next_node # The new head is the last node we processed return prev</code>

Fungsi ini mengambil kepala senarai yang dipautkan sebagai input dan mengembalikan kepala baru senarai terbalik. Ia menggunakan tiga petunjuk ( prev , current , dan next_node ) untuk membalikkan pautan antara nod.

Apakah kerumitan masa membalikkan senarai yang dipautkan?

Kerumitan masa membalikkan senarai yang dipautkan ialah O (n), di mana n ialah bilangan nod dalam senarai. Ini kerana kita perlu melintasi setiap nod tepat sekali untuk membalikkan pautan. Operasi dalam gelung (membalikkan pautan dan menggerakkan petunjuk) adalah operasi masa yang berterusan, jadi jumlah masa yang diambil adalah berkadar dengan panjang senarai.

Bolehkah anda menerangkan proses langkah demi langkah untuk membalikkan senarai yang dipautkan?

Membalikkan senarai yang dipautkan melibatkan perubahan arah setiap penunjuk next nod. Berikut adalah penjelasan langkah demi langkah mengenai proses:

1. Memulakan penunjuk:

   • prev pada mulanya ditetapkan kepada None (ini akan menjadi kepala baru selepas pembalikan).
   • current ditetapkan ke kepala senarai asal.
   • next_node digunakan buat sementara waktu untuk menyimpan nod seterusnya.

2. Melintasi senarai:

   • Walaupun current tidak None , lakukan perkara berikut:
     a. Tetapkan next_node ke current.next (simpan nod seterusnya sebelum kita menukar pautan).
     b. Tetapkan current.next ke prev (membalikkan pautan).
     c. Pindah ke prev ke current (prev menjadi nod yang kita hanya diproses).
     d. Pindahkan current ke next_node (pindah ke nod seterusnya dalam senarai asal).

3. Lengkapkan pembalikan:

   • Selepas gelung berakhir, prev akan menunjuk ke nod terakhir senarai asal, yang kini menjadi ketua baru senarai terbalik.

4. Kembalikan kepala baru:

   • prev sebagai ketua baru senarai terbalik.

Proses ini secara berkesan membalikkan arah semua pautan dalam senarai, menjadikan nod terakhir ke kepala baru dan kepala asal ke ekor baru.

Bagaimanakah membalikkan senarai yang dipautkan mempengaruhi traversalnya?

Membalikkan senarai yang dipautkan mengubah urutan di mana nod diakses semasa traversal. Inilah caranya mempengaruhi traversal:

1. Arah Traversal:

   • Sebelum pembalikan, melintasi kepala ke ekor bermakna melawat nod mengikut urutan yang pada asalnya ditambah.
   • Selepas pembalikan, melintasi kepala baru (ekor asal) ke ekor baru (kepala asal) bermaksud melawat nod dalam urutan terbalik penambahan asalnya.

2. Akses nod:

   • Nod yang berada di awal senarai sebelum pembalikan kini akan berada di akhir, dan sebaliknya.
   • Ini bermakna jika anda mengakses beberapa nod pertama senarai yang kerap sebelum pembalikan, selepas pembalikan, anda perlu melintasi hampir keseluruhan senarai untuk mengakses nod yang sama.

3. Implikasi Algoritma:

   • Algoritma yang bergantung kepada susunan nod dalam senarai perlu diselaraskan.
   • Sebagai contoh, algoritma carian yang mengharapkan nod berada dalam perintah tertentu perlu diubah suai untuk mengambil kira perintah yang diterbalikkan.

4. Prestasi:

   • Kerumitan masa melintasi keseluruhan senarai kekal o (n), tetapi nod tertentu yang diakses pada bila -bila masa semasa traversal akan berbeza.

Ringkasnya, membalikkan senarai yang dipautkan secara asasnya mengubah struktur senarai, yang mempengaruhi bagaimana ia dilalui dan bagaimana algoritma yang beroperasi pada senarai perlu dilaksanakan.

Atas ialah kandungan terperinci Melaksanakan fungsi untuk membalikkan senarai yang dipautkan.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!