24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

---

交换链表的每两个相邻节点。样例不保证是偶数个节点，也可能出现奇数个节点，此时最后一个节点就不要交换了。 交换过程中需要使用3个指针，当前指针ln1，当前指针的下一个指针ln2以及ln1的副本ln3用于更改ln1的next。具体怎么变换的，在纸上画一画就知道了，下面是完整代码。

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *ln1 = head, *ln2 = ln1->next, *ln3 = ln1, *new_head = ln2;
        bool first = true;
        while (ln1) {
            ln2 = ln1->next;
            if (ln2 == NULL)
                break;
            ln1->next = ln2->next;
            ln2->next = ln1;
            if (!first) { // 第一次不需要更改ln3的指向
                ln3->next = ln2;
            }
            first = false;
            ln3 = ln1;
            ln1 = ln1->next;
        }
        return new_head;
    }
};

本代码提交AC，用时4MS，只击败了1.83%，郁闷，我这已经是O(n)的时间复杂度，O(1)的空间复杂度，不知道还可以怎样优化。

更漂亮的递归版本：

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

本代码提交AC，用时6MS，无语了。