Given a linked list, swap every two adjacent nodes and return its head.

Example:


Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:


       Your algorithm should use only constant extra space.
       You may not modify the values in the list's nodes, only nodes itself may be changed.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         i = 1
         node = head
         prev = None
         prev2 = None
         while node is not None:
             if i % 2 == 0 and i != 1:
                 if prev2 is not None:
                     prev2.next = node
                 prev.next = node.next
                 node.next = prev
                 if i == 2:
                     head = node
                 node = prev
             prev2 = prev
             prev = node
             node = node.next
             i += 1
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if head == None:
             return head
         
         i = head
         j = head.next
         k = None
         
         while i != None and j != None:
             
             i.next = j.next
             j.next = i
             
             if i == head:   # reposition head if we're at the front of the list
                 head = j
             
             if k:           # if we have a trailing node, link j into LL
                 k.next = j
                 
             # update node pointers
             if i.next != None:  
                 j = i.next.next 
                 k = i
             
             i = i.next
             
         return head
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         pre, pre.next = self, head
         
         while pre.next and pre.next.next:
             
             a = pre.next
             b = a.next
             pre.next, b.next, a.next = b, a, b.next
             pre = a
             
         return self.next
             
         

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

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
 
         if head is None or head.next is None:
             return head
         else:
             first = head
             second = first.next
             third = second.next
 
             second.next = first
             first.next = self.swapPairs(third)
             return second

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     # Iteratively
     def swapPairs(self, head):
         r = p = ListNode(0)
         r.next = head
 
         '''
             h h.n h.n.n
         '''
         while head and head.next:
             t = head.next
 
             head.next = t.next
             t.next = head
 
             p.next = t
             
             p = t.next
             head = head.next
 
         return r.next
 
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         
         def swapTwo(head):
             if not head.next:
                 return head
             elif not head.next.next:
                 tmp = head.next
                 head.next = None
                 tmp.next = head
                 return tmp
             else:
                 tmp = head.next
                 head.next = swapTwo(tmp.next)
                 tmp.next = head
                 return tmp
         
         if not head:
             return head
         else:
             return swapTwo(head)

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         root = p = ListNode(0);
         while head:
             a = head;
             if head.next:
                 b = head.next;
                 p.next = ListNode(b.val);
                 p = p.next;
                 p.next = ListNode(a.val);
                 p = p.next;
                 head = head.next.next;
             else:
                 p.next = ListNode(a.val);
                 head = a.next;
         return root.next
         
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         dummy = ListNode(None)
         previous = dummy
         previous.next = head
         node = head
         while node and node.next:
             end = node.next.next
             previous.next = node.next
             node.next.next = node
             node.next = end
             previous = previous.next.next
             node = previous.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
 
         dummy = ListNode(None)
         prev = dummy
         dummy.next = head
 
         left = head
         while left:
           if left.next is None:
             break
           right = left.next
           prev.next = right
           left.next, right.next = right.next, left
           prev = left
           left = left.next
 
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         
         if head is None:
             return []
         elif head.next is None:
             return head
         
         itr1 = head
         itr2 = head.next
         prev = itr1
         head = itr2
         d = head
         
         while itr1 is not None and itr2 is not None:
             temp = itr2.next
             itr2.next = itr1
             itr1.next = temp
             itr1 = itr1.next
             if itr1 is not None:
                 itr2 = itr1.next
                 if itr2 is None:
                     prev.next = itr1
                 else:
                     prev.next = itr2
                 prev = itr1
 
 
             print("=========")
             
             while d is not None:
                 print(d.val)
                 d = d.next
             d = head
             print("===========")
             
 
             
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def swapPairs(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         guard = ListNode(0)
         guard.next = head
         prev = guard
         cur = head
         while cur != None and cur.next != None:
             nxt = cur.next
             print(prev.val, cur.val, nxt.val)
             # do swap
             cur.next = nxt.next
             nxt.next = cur
             prev.next = nxt
             # move forward
             prev = cur
             cur = cur.next
             
             tmp = guard
             while tmp:
                 print(tmp.val)
                 tmp = tmp.next
         return guard.next