Swap Nodes in Pairs

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* swap(ListNode *head) {

        ListNode *tmp = head->next;

        tmp->next = head;

        head->next = nullptr;

        return tmp;

    }

   

    ListNode *swapPairs(ListNode *head) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

       

        ListNode *dummy = new ListNode(0);  //Note: using a dummy node

        ListNode *ptr = head, *nxt = head;

        ListNode *dhead = dummy;

       

        while(ptr != nullptr) {

            if(ptr->next != nullptr) {  //Note: be careful about the pointer update

                nxt = ptr->next->next;

                dhead->next = swap(ptr);

                dhead = ptr;

                ptr = nxt;

            } else {  // Note: deal with the single node

                dhead->next = ptr;

                ptr = ptr->next;

            }

        }

       

        dhead = dummy->next;

        delete dummy;

        return dhead;

    }

};