Swap every two nodes in linked list

Question

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

# Definition for singly-linked list.
 class ListNode(object):
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur =head
        while cur and cur.next:
            nxtPair=cur.next.next 
            second=cur.next
            cur.next=nxtPair
            second.next=cur
            cur=second 
            cur=cur.next.next       
        return head 

   input:[1,2,3,4]
   output:
   [1,3]
   expected:
   [2,1,4,3]

I found a solution using dummy linkedlist but without using dummy linkedlist I didn't understand what mistake I made. To have more clarity on this concept can anyone help me with this problem.Here head is not being updated for example , If I have to swap 1,2 to 2,1..head is not being updated to 2,1 instead having only node with 1 as value

Answer 1

There is something different about the first pair swap as opposed to all pair swaps afterward: the first pair swap does not have a predecessor, but so you only need to update two linkages (and remember to change the head), while future updates require you to go back to the predecessor and update it, and so you need three linkage updates.

So there is some special handling of the first case. You could either give the list a dummy head so that the first swap updates its predecessor just like the rest of the swaps, or you can peel off the first loop like this:

def swapPairs(head):
    if head and head.next:
        # Before: (head=c1) --> c2 --> c3
        #  After: (head=c2) --> c1 --> c3
        c1 = head
        c2 = c1.next
        c3 = c2.next
        head = c2
        c2.next = c1
        c1.next = c3
        cur = c1

        while cur.next and cur.next.next:
            # Before: cur --> c1 --> c2 --> c3
            #  After: cur --> c2 --> c1 --> c3
            c1 = cur.next
            c2 = c1.next
            c3 = c2.next
            cur.next = c2
            c2.next = c1
            c1.next = c3
            cur = c1

    return head

(or you could keep a "prev" variable and add an "if this isn't the first loop..." condition, like in Andrew Parmar's solution)