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

 

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.

 

LeetCode上的原题，请参见我之前的博客。

 

解法一：

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

 

解法二：

class Solution {public:    /**     * @param head a ListNode     * @return a ListNode     */    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;    }};