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.

code :

 

/** * 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) {        // Note: The Solution object is instantiated only once and is reused by each test case.        if(head == NULL)            return NULL;        if(head->next == NULL)            return head;                ListNode *p = head;        ListNode *q = head->next;        ListNode *pre = NULL;        while( q != NULL && q->next != NULL)      // p,q 指向相邻结点一前一后        {                                        // 注意奇数个结点的情况，判空为第一种            ListNode *tmp = q->next;            q->next = p;            p->next = tmp;            if( pre == NULL)            {                head = q;                pre = p;            }            else            {                pre->next = q;                pre = p;            }            p = p->next;            q = p->next;        }        if(pre == NULL)     //只有两个结点        {            head = q;            q->next = p;            p->next = NULL;            return head;        }        if(q == NULL)       //奇数个结点        {            return head;        }        q->next = p;        //偶数个结点        p->next = NULL;        pre->next = q;        return head;            }};