Python – swapping pairs in Python’s linked list and a link disappears?

swapping pairs in Python’s linked list and a link disappears?… here is a solution to the problem.

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()

Related Problems and Solutions