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 *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode* h = dummy;
        
        
        ListNode *tmp1 = NULL, *tmp2 = NULL, *tmp3 = NULL;
        while (h->next && h->next->next)
        {
            tmp1 = h->next;
            tmp2 = h->next->next;
            tmp3 = h->next->next->next;
            
            h->next = tmp2;
            tmp2->next = tmp1;
            tmp1->next = tmp3;
            
            h = tmp1;
        }
        
        ListNode* res= dummy->next;
        delete dummy;
        return res;     
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s