Permuter des paires dans une liste chaînée en Python, un lien disparaît?

Question

J'ai appris à propos des listes chaînées, et l'implémentation d'une en python a été plus facile que prévu. Cependant, quand il est venu à résoudre le problème de "échanger des paires dans une liste liée", pour une raison quelconque mon deuxième lien disparaît pendant le swap. J'ai regardé cela pendant des lustres et essayé différentes solutions que j'ai trouvées en ligne. Ils obtiennent tous le même résultat, ce qui suggère que mon problème est lié à l'implémentation de la liste elle-même. Ou j'ai fait une erreur stupide quelque part que je ne peux pas voir! Je serais reconnaissant pour une nouvelle paire d'yeux. Qu'est ce que j'ai mal fait?

class Node: 
    def __init__(self, val): 
     self.value = val 
     self.next = None 

class LinkedList: 
    def __init__(self, data): 
     self.head = Node(data) 

    def printList(self, head): 
     while head: 
      print("->" , head.value) 
      head = head.next; 

    def swapPairsR(self, node): # recursive 
     if node is None or node.next is None: 
      return node 
     ptrOne = node 
     ptrTwo = node.next 
     nextPtrTwo = ptrTwo.next 

     # swap the pointers here at at the rec call 
     ptrTwo.next = node 
     newNode = ptrTwo 

     ptrOne.next = self.swapPairsR(nextPtrTwo) 
     return newNode 

    def swapPairsI(self, head): # iterative 
     prev = Node(0) 
     prev.next = head 
     temp = prev 

     while temp.next and temp.next.next: 
      ptrOne = temp.next 
      ptrTwo = temp.next.next 

      # change the pointers to the swapped pointers 
      temp.next = ptrTwo 
      ptrOne.next = ptrTwo.next 
      ptrTwo.next = ptrOne 
      temp = temp.next.next 

     return prev.next 

thisLList = LinkedList(1) 
thisLList.head.next = Node(2) 
thisLList.head.next.next = Node(3) 
thisLList.head.next.next.next = Node(4) 
thisLList.head.next.next.next.next = Node(5) 
thisLList.printList(thisLList.head) 
print("--------------") 
thisLList.swapPairsI(thisLList.head) 
thisLList.printList(thisLList.head) 

Edit: ma sortie:

-> 1 
-> 2 
-> 3 
-> 4 
-> 5 
-------------- 
-> 1 
-> 4 
-> 3 
-> 5 

Answer 1

Votre fonction swapPairsI retourne la nouvelle head de votre liste chaînée. Vous devez mettre à jour en conséquence:

thisLList.head = thisLList.swapPairsI(thisLList.head) 

---

Ou mieux encore, vous devriez changer votre fonction swapPairsI afin qu'il ne doit pas prendre un nœud en tant que paramètre:

def swapPairsI(self): # iterative 
    prev = Node(0) 
    prev.next = self.head 
    temp = prev 

    while temp.next and temp.next.next: 
     ptrOne = temp.next 
     ptrTwo = temp.next.next 

     # change the pointers to the swapped pointers 
     temp.next = ptrTwo 
     ptrOne.next = ptrTwo.next 
     ptrTwo.next = ptrOne 
     temp = temp.next.next 

    self.head = prev.next 

En Dans ce cas, vous pouvez simplement appeler:

thisLList.swapPairsI()