A short iterative solution with pointer of pointer.


  • 0
    A
     /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
     
     /*
     a linked list is like this.
      ---------------------------------------
      |  p |  +->| c1 |  +->| c2 |  +->|  n |
      --------|----------|----------|---------
      |  * |--+  |  * |--+  |  * |--+  |  * |
      ---------------------------------------   
     */
         class Solution {
         public:
                ListNode* swapPairs(ListNode* head) {
                ListNode** a=&head;
                ListNode** b;
                ListNode* temp;
               while ((*a) && (*a)->next) {
      /*
      at begining. we want to swap c1 and c2.
      ---------------------------------------
      |  p |  +->| c1 |  +->| c2 |  +->|  n |
      --------|----------|----------|---------
      |  * |--+  |  * |--+  |  * |--+  |  * |
      ---------------------------------------   
         ^
         |  
      |  a |
     
     */
                b=&((*a)->next);
     /*
      after above
      ---------------------------------------
      |  p |  +->| c1 |  +->| c2 |  +->|  n |
      --------|----------|----------|---------
      |  * |--+  |  * |--+  |  * |--+  |  * |
      ---------------------------------------   
         ^          ^
         |          | 
      |  a |     |  b |
     
     */
                temp=*a;
     /*
      after above
                 |temp|
                   |
                   v
      ---------------------------------------
      |  p |  +->| c1 |  +->| c2 |  +->|  n |
      --------|----------|----------|---------
      |  * |--+  |  * |--+  |  * |--+  |  * |
      ---------------------------------------   
         ^          ^
         |          | 
      |  a |     |  b |
     
     */
                *a = &(**b);
     /*
      after above
                 |temp|
                   |
                   |
              +----|----------+
              |    |          |
              |    v          v
      --------|------------------------------
      |  p |  |  | c1 |  +->| c2 |  +->|  n |
      --------|----------|----------|---------
      |    |--+  |    |--+  |    |--+  |    |
      ---------------------------------------   
         ^          ^
         |          | 
      |  a |     |  b |
     
     */
                *b = (*b)->next;
     /*
      after above
                 |temp|
                   |
                   |
              +----|----------+
              |    |     +----|----------+
              |    v     |    v          v
      --------|----------|-------------------
      |  p |  |  | c1 |  |  | c2 |  +->|  n |
      --------|----------|----------|---------
      |    |--+  |    |--+  |    |--+  |    |
      ---------------------------------------   
         ^          ^
         |          | 
      |  a |     |  b |
     
     */
                (*a)->next=temp;
     /*
      after above
                 |temp|
                   |
                   +----------------+
              +----|----------+     |
              |    |     +----|-----|----+
              |    v     |    v     |    v
      --------|----------|----------|--------
      |  p |  |  | c1 |  |  | c2 |  |  |  n |
      --------|----------|----------|---------
      |    |--+  |    |--+  |    |--+  |    |
      ---------------------------------------   
         ^          ^
         |          | 
      |  a |     |  b |
     
     which is: 
                            |temp|
                              |
                              v
      ---------------------------------------
      |  p |  +->| c2 |  +->| c1 |  +->|  n |
      --------|----------|----------|---------
      |  * |--+  |  * |--+  |  * |--+  |  * |
      ---------------------------------------   
         ^                     ^
         |                     | 
      |  a |                |  b |
     
     
     */
                a=b;
            }
            return head;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.