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.

C++:
01 /**
02  * Definition for singly-linked list.
03  * struct ListNode {
04  *     int val;
05  *     ListNode *next;
06  *     ListNode(int x) : val(x), next(NULL) {}
07  * };
08  */
09 
10 class Solution {
11 public:
12     ListNode *swapPairs(ListNode *head) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         if((head==NULL)||(head->next==NULL ) )
16             return head;
17         ListNode* hd=head->next;
18         ListNode* prv=NULL;
19         for(ListNode* p=head;p!=NULL😉
20         {
21             ListNode* x=p->next;
22             if(x==NULL)
23             {
24                 if(prv!=NULL)
25                     prv->next=p;
26                 break;
27             }
28             ListNode* y=x->next;
29             if(prv!=NULL) prv->next=x;
30             x->next=p;
31             p->next=NULL;
32             prv=p;
33             p=y;
34         }
35         return hd;
36     }
37 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s