Saya memiliki kelas ListNode berikut:

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

Saya menulis kode berikut dengan tujuan menghapus duplikat dari daftar yang ditautkan:

def deleteDuplicates(self, head: ListNode) -> ListNode:      
    if head == None: 
        return None 
    if head.next == None: 
        return head 
    curr = head 
    nex = head.next 
    while nex: 
        if head.val == nex.val: 
            curr.next = nex.next
        curr = nex.next
        nex = curr.next

Pertanyaan:

  1. Apa yang saya kembalikan pada akhirnya? Apakah ini 'kepala' atau 'curahan' atau sesuatu yang lain? Dan mengapa? - Saya tahu bahwa saya ingin output menjadi daftar input yang ditautkan tetapi dengan duplikat dihapus; Jadi, apakah masuk akal untuk mengembalikan kepala daftar yang ditautkan? Tetapi ketika saya melakukan ini, saya tidak cukup mendapatkan hasil yang diharapkan, yaitu [1,1,2,2,3,3] - & gt; [1,2,3,3]; Yang menuntun saya untuk pertanyaan saya berikutnya ...

  2. Apakah saya perlu menulis case tepi ketika ada duplikat tepat di akhir daftar tertaut? Karena saya tidak percaya kode saya di bawah ini berurusan dengan ini - apakah saya benar?

0
odablocker 5 April 2021, 12:07

1 menjawab

Jawaban Terbaik

Saya akan berasumsi bahwa daftar Anda selalu diurutkan, sehingga setiap duplikat selalu duduk di samping satu sama lain dalam daftar.

Ada dua masalah di loop while Anda:

  1. Anda harus membandingkan nilai-nilai dari dua yang berdekatan node, tetapi kode Anda selalu membandingkan nilai berikutnya dengan nilai node kepala. Jadi ubah:

    if head.val == nex.val: 
    

    untuk

    if curr.val == nex.val: 
    
  2. Kode Anda melewatkan node dengan melakukan curr = nex.next. Ini berarti curr tidak akan pernah nex. Ini juga memiliki efek bahwa pernyataan selanjutnya mungkin referensi yang tidak valid, sebagai curr mungkin None. Jadi ubah:

    curr = nex.next
    

    untuk

    curr = nex
    
  3. Ketika Anda mendeteksi duplikat, hanya nex harus pindah ke node berikutnya. curr harus tetap di mana itu, karena mungkin memiliki lebih dari satu duplikat untuk dihadapi. Jadi penugasan di atas untuk curr seharusnya hanya terjadi ketika Anda tidak memiliki duplikat.

Loop while yang dikoreksi adalah sebagai berikut:

while nex:
    if curr.val == nex.val: 
        curr.next = nex.next
    else:
        curr = nex
    nex = curr.next

Apa yang harus kembali

Karena fungsi Anda tampaknya dirancang untuk kembali a ListNode, pastikan untuk selalu return head. Jadi tambahkan pernyataan itu juga setelah loop while.

Menurut pendapat saya seharusnya tidak diperlukan untuk fungsi ini untuk mengembalikan simpul kepala, karena nilai head akan tidak pernah berubah dengan fungsi ini. Jadi penelepon sudah tahu nilainya.

NB: Anda tidak perlu berurusan secara khusus dengan kasus ini:

if head.next == None: 
   return head 

Kasus ini hanya berarti bahwa loop while tidak akan memiliki satu iterasi tunggal. Seperti yang dikatakan di atas, cukup tambahkan pernyataan kembali pada akhir fungsi, dan kemudian Anda dapat menjatuhkan blok if di atas:

return head
1
trincot 5 April 2021, 09:53