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.
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode* swapPairs(ListNode* head) {
12
13 if(head == NULL || head->next == NULL){
14 return head;
15 }
16 ListNode* newHead = new ListNode(-1);
17 ListNode* tail = newHead;
18 newHead->next = head;
19
20 while(tail && tail->next && tail->next->next){
21 ListNode* n = tail->next;
22 ListNode* nn = tail->next->next;
23
24 //tail->next = nn;
25 n->next = nn->next;
26 nn->next = n;
27 tail->next = nn;
28
29 tail = tail->next->next;
30 }
31
32 return newHead->next;
33 }
34 };