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.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode *swapPairs(ListNode *head) {

        if(head == NULL || head->next == NULL)

            return head;

        ListNode dummy(0);

        ListNode *tail = &dummy;

        ListNode *pre = head;

        ListNode *cur = NULL;

        ListNode *nxt = NULL;

        while(pre != NULL)

        {

            cur = pre->next;

            if(cur != NULL)

            {

                nxt = cur->next;

                cur->next = pre;

                pre->next = NULL;

                tail->next = cur;

                tail = pre;

                pre = nxt;

            }

            else

            {

                tail->next = pre;

                return dummy.next;

            }

        }

        return dummy.next;

    }

};