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.

　　这题不难，直接贴两个我中意的代码：

solution1：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* swapPairs(ListNode *head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *list = head->next;
    head->next = swapPairs(list->next);
    list->next = head;
    return list;
}

参考链接：https://leetcode.com/discuss/16246/my-simple-recursive-solution

solution2：

ListNode* swap(ListNode *next1, ListNode *next2)
{
    next1->next = next2->next;
    next2->next = next1;
    return next2;
}

ListNode* swapPairs(ListNode *head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *start = new ListNode(0);
    start->next = head;
    for (ListNode *cur = start;cur->next && cur->next->next;cur = cur->next->next)
    {
        cur->next = swap(cur->next, cur->next->next);
    }
    return start->next;
}

ps:

　　递归解法真的很赞，有木有。