Python-logica van ListNode in Leetcode

Hier is de definitie van de klasse ListNotein LeetCode:

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

Voor de code:

result = ListNode(0)
#result = 0 -> None
result_tail = result
#result_tail = 0 -> None
result_tail.next = ListNode(1)
#result_tail = 0 -> 1 -> None
#result = 0 -> 1 -> None
result_tail = result_tail.next
#result_tail = 1 -> None
#result = 0 -> 1 -> None
result_tail.next = ListNode(2)
#result_tail = 1 -> 2 -> None
#result = 0 -> 1 -> 2 -> None
result_tail = result_tail.next
#result_tail = 2 -> None
#result = 0 -> 1 -> 2 -> None

De waarden in opmerkingen zijn naar mijn idee. Ik begrijp de stap niet

result_tail = result_tail.next

result_tail = resultwordt doorgegeven als referentie, dus wanneer result_tail1 -> None, resultmoet ook 1 -> None. Waarom behoudt result0 -> 1 -> None? En wanneer result_tail1 -> 2 -> None, waarom breidt resultzijn staart uit naar 0 -> 1 -> 2 -> None?

result_tail = result_tail.next

Is zoiets als

result_tail = result.next.next    

Kan iemand me de logica hier vertellen?

Antwoord 1, autoriteit 100%

Het korte antwoord hierop is dat Python een pass-by-object-referentietaal is, geen pass-by-referentie zoals geïmpliceerd in de vraag. Het betekent dat:

1. resulten result_tailzijn twee variabelen die toevallig naar dezelfde waarde wijzen
2. Mutatie / wijziging van de onderliggende waarde (result_tail.next = ListNode(1)) heeft invloed op de waarde getoond door result
3. Het toewijzen/verwijzen van de variabele result_tailaan een andere waarde heeft echter GEEN invloed op de waarde van result
4. result_tail = result_tail.nextwijst het volgende knooppunt van het knooppunt toe dat momenteel is toegewezen door de variabele

Het volgende is een visualisatie van de waarden die aan de variabelen zijn toegewezen (r= result, rt= result_tail):

result = ListNode(0)
#r
#0 -> None
result_tail = result
#r
#0 -> None
#rt
result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt
result_tail = result_tail.next
#r
#0 -> 1 -> None
#     rt
result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
#     rt
result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
#          rt

Referenties voor aanvullende informatie:

• Een artikel waarin de Python pass-by-object-referentiestijl in detail wordt uitgelegd https://roberheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick /
• Een antwoord waarin de pass-by-object-referentiestijl van Python wordt uitgelegd https://stackoverflow.com/a/33066581/12295149
• Vraag over de objectreferentiestijl van Python De call-by-object-stijl van Python voor het doorgeven van functieargumenten begrijpen

Antwoord 2, autoriteit 22%

Ten eerste hartelijk dank voor het plaatsen van deze vraag. Ik werkte aan hetzelfde probleem en zag dit stukje code en was ook verbaasd. Toen volgde ik enkele opmerkingen van leetcode en kwam hier terecht.

Ik realiseer me dat mijn probleem was dat ik eerder geen pen en papier had. Nadat ik de gelinkte lijst op het papier had getekend door de lus te volgen, bleek het vrij duidelijk te zijn.

Als je hier nog steeds niet duidelijk over bent, probeer dan de gelinkte lijst te tekenen door de logica te volgen. Ik weet niet zeker of ik de juiste term hier heb, maar hieronder is mijn begrip.

Om eerlijk te zijn, denk ik niet dat dit te maken heeft met pass-by-referentie of waarde. Voor mij zijn dit zo ongeveer twee variabelen die aan het begin dezelfde waarde (geheugenlocatie) krijgen. Beschouw variabelen als opslag van adres. Adres is de echte geheugenlocatie die het begin is van een bepaalde waarde. Later werd één variabele (result_tail) steeds opnieuw toegewezen aan een andere locatie en één (resultaat) bleef hetzelfde.

Result en result_tail wijzen beide naar de locatie van 0|None vóór de while-lus.
0|Nonegroeide uit tot 0->7|None, daarna 0->7->0|Noneen ten slotte 0->7->0->8|Nonedoor result_tail.next wordt elke keer toegewezen. Result_tail wordt opnieuw toegewezen, dus de waarde wordt tijdens elke lus gewijzigd, maar het resultaat wijst naar dezelfde locatie, namelijk de 0->....Dus het resultaat.

Antwoord 3, autoriteit 22%

Voor degenen die dit in de toekomst lezen: ik wilde problemen met gekoppelde lijsten opsporen in een lokale omgeving, dus dit is wat ik deed.

1. De Leetcode-code voor ListNode gewijzigd door de dunder “repr“-methode op te nemen. Dit is voor wanneer u een ListNode wilt afdrukken om te zien wat de waarde is en de volgende node(s).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def __repr__(self):
        return "ListNode(val=" + str(self.val) + ", next={" + str(self.next) + "})"

2. Vervolgens heb ik een recursieve functie gemaakt die een geneste ListNode maakt wanneer je in een lijst komt. Dit is zodat u uw methoden kunt testen door lijsten door te geven (in plaats van zelf handmatig een verwarrend uitziende ListNode te moeten maken.

def list_to_LL(arr):
    if len(arr) < 1:
        return None
    if len(arr) == 1:
        return ListNode(arr[0])
    return ListNode(arr[0], next=list_to_LL(arr[1:]))

3. Hier is een voorbeeld dat mijn antwoord op het “reverseList”-probleem test:

def reverseList(head: ListNode) -> ListNode:
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node
    return prev
# test cases
t1 = list_to_LL([1, 2, 3, 4, 5])  #ListNode(val=1, next={ListNode(val=2, next={ListNode(val=3, next={ListNode(val=4, next={ListNode(val=5, next={None})})})})})
t2 = list_to_LL([1, 2])  #ListNode(val=1, next={ListNode(val=2, next={None})})
t3 = list_to_LL([])
# answers
print(reverseList(t1))
print(reverseList(t2))
print(reverseList(t3))

Antwoord 4

Alle bovenstaande antwoorden lijken goed. Ik tel slechts een voorbeeld op voor het begrip van de lezer.

Invoer gegeven: [[1,4,5],[1,3,4],[2,6]]

ListNode objectbeschrijving:

[ListNode{val: 1, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}, ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}, ListNode{val: 2, next: ListNode{val: 6, next: None}}]

Hopelijk heb je de CRUX!