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.

这一题要求两两交换链表中的元素。题目要求常数时间，即无法使用递归解法。

主要思路是两个两个结点<node1,node2>进行处理，为了维护连接，需要维护一个prev头元素，操作之前指向node1,操作之后指向node2。为了防止头元素的问题，需要再次用到dummy技巧。每次处理时，实际是需要将prev->node1,node1->node2,node2->node2.next这三条指向进行重定向，先交换的不能影响后续交换需要用到的连接，实际操作时可以画个图来具体看看先后顺序。时间复杂度O(n),空间复杂度O(1)。代码如下：

class Solution(object):    def swapPairs(self, head):        """        :type head: ListNode        :rtype: ListNode        """        if not head or not head.next:            return head        dummy = ListNode(-1)        dummy.next = head        prev = dummy        cur = head         while cur and cur.next:                        prev.next = cur.next            cur.next = prev.next.next            prev.next.next = cur            prev = cur            cur = cur.next        return dummy.next