Leetcode: Swap Nodes in Pairs (4ms)

problem

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.

Hide Tags

 Linked List

Show Similar Problems

------------------------

-----------------------

1. create a dummy node for head

2. exchange two nodes

class Solution {

public:

       ListNode* swapPairs(ListNode* head) {

              //check input

              if (head == NULL) return NULL;//empty list node  

              if (head->next == NULL) return head; // one list node

              ListNode* t1, *t2, *t3, *tmp, *pre = new ListNode(-1);

              pre->next = head;

              t1 = head;

              head = pre;

              while (1){

                     if (t1->next != NULL){

                           //keep previous value

                           t2 = t1->next;

                           t3 = t2->next;

                           //exchange two nodes

                           tmp = t2;

                           tmp->next = t1;

                           tmp->next->next = t3;

                           //connect to prevous node

                           pre->next = tmp;

                           //prepare for next loop

                           pre = t1;

                           t1 = t3;

                           if (t3 == NULL || t3->next == NULL) break;

                     }

              }

              return head->next;

       }

};