swapping pairs in Python’s linked list and a link disappears?
I’ve been learning linked lists and implementing linked lists in Python is easier than I expected. However, when solving the “swap pair in linked list” issue, for some reason my second link disappeared during the swap process. I’ve been staring at this for a long time and tried different solutions that I found online. They all get the same result, which shows that my problem lies in the implementation of the list itself. Or maybe I made a stupid mistake somewhere that I can’t see! I would appreciate it if there were a fresh pair of eyes. What am I doing wrong?
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: My Output:
-> 1
-> 2
-> 3
-> 4
-> 5
--------------
-> 1
-> 4
-> 3
-> 5
Solution
Your swapPairsI
function is returning a new head
for the linked list.
You need to update it accordingly:
thisLList.head = thisLList.swapPairsI(thisLList.head)
Or better yet, you should change the swapPairsI
function so that it doesn’t have to take the node as a parameter:
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
In this case, you can simply call:
thisLList.swapPairsI()