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

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

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        return self.swapPairs_3

    def swapPairs_1(self, head):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while head and head.next:
          prev.next = head.next
          head.next = head.next.next
          prev.next.next = head
          prev = head
          head = head.next
        return dummy.next

    def swapPairs_2(self, head):
        if head.next is None or head.next.next is None:
            return
        move = head.next.next
        head.next.next = move.next
        move.next = head.next.next
        head.next = move
        self.swapPairs_2(move.next)

    def swapPairs_3(self, head):
        if head is None or head.next is None:
            return head
        first = head
        second = head.next
        first.next = second.next
        second.next = first
        first.next = self.swapPairs_3(first.next)
        return second

@@ -4,17 +4,17 @@
 %0AGiven a
- 
+%C2%A0
 linked l
@@ -74,129 +74,8 @@
 d.%0A%0A
-For example,%0AGiven 1-%3E2-%3E3-%3E4, you should return the list as 2-%3E1-%3E4-%3E3.%0A%0AYour algorithm should use only constant space. 
 You 
@@ -111,16 +111,24 @@
 the list
+'s nodes
 , only n
@@ -143,11 +143,11 @@
 elf 
-can
+may
  be 
@@ -154,16 +154,87 @@
 changed.
+%0A%0AExample:%0A%0AGiven 1-%3E2-%3E3-%3E4, you should return the list as 2-%3E1-%3E4-%3E3.
 %0A%22%22%22%0A%0A# 
@@ -1368,8 +1368,432 @@
  second%0A
+%0A    def swapPairs_3(self, head):%0A        # used one more variable%0A        dummy = ListNode(0)%0A        dummy.next = head%0A        current = head%0A        prev = dummy%0A        while current and current.next:%0A            next = current.next%0A            prev.next = next%0A            current.next = next.next%0A            next.next = current%0A            prev = current%0A            current = current.next%0A%0A        return dummy.next%0A

Update 24