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.

Tag: linked list

 

一个简单的链表练习。常数空间，所以指针，时间复杂度o(n)。

先判断输入为空或只有一个节点的情形。

再把第一对节点单独处理，因为之后的节点需要先交换，再把前一对的节点连接到当前节点上，比第一对节点多了一步处理步骤。

C++代码：

/**
 * 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) {
        ListNode * p = head;
        ListNode * q = NULL;
        
        /*handle empty input*/
        if (head == NULL || head->next == NULL){
            return head;
        }
        
        /*handle first two nodes*/
        head = p->next;
        p->next = head->next;
        head->next = p;
        
        /**
         * line 34: p is the last node of previous swapped pair
         * line 35: set q to the fist node of current pair
         * line 36: link p->next to the second node of current pair
         * line 37: move p to the second node of current pair
         * line 38: link q->next to the first node of next pair
         * line 39: link p->next to the first node of current pair (q)
         * line 40: set p to the second node of current swapped pair
         **/
        while (p->next != NULL && p->next->next != NULL){ //judge from left to right
            q = p->next;
            p->next = q->next;
            p = p->next;
            q->next = p->next;
            p->next = q;
            p = q;
        }
        return head;
    }
};

程序效率