24. Swap Nodes in Pairs

这道题意思是，给出一个链表，把每一对相邻节点交换，并且不允许改变节点内部的val值，空间复杂度是常量级。

我定义了三个指针abc，b和c指向要交换的两个节点，a指向要交换的那一对节点的前面一个节点。每次交换b和c，然后把a更新到b（注意交换完了之后，后面的节点变成b而不是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) {
        if(head == NULL)    return NULL;
        if(head->next == NULL)  return head;
        ListNode* newhead = new ListNode(-1);
        newhead->next = head;
        ListNode* a = newhead;
        ListNode* b = newhead->next;
        ListNode* c = newhead->next->next;
        while(a != NULL && b != NULL && c != NULL){
            cout << a->val << " "<< b->val << " "<< c->val << endl;
            a->next = c;
            b->next = c->next;
            c->next = b;
            a = b;
            b = a->next;
            c = (b == NULL)?NULL:b->next;
        }
        return newhead->next;
    }
};

看到有更简单的代码，方法一样的：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next && pre->next->next) {
            ListNode *t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

还有用递归做的，更简单：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *t = head->next;
        head->next = swapPairs(head->next->next);
        t->next = head;
        return t;
    }
};