leetcode算法第24题，难度为medium。将链表中的节点成对翻转，考察链表结构的理解和节点的操作。

Description

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.

Note:

  • Your algorithm should use only constant extra space.
  • You may not modify the values in the list's nodes, only nodes itself may be changed.

来源：leetcode 24 swap nodes in pairs

Solution

Apporach 1

这道题还是对链表操作的考察，在熟悉链表之后还是比较容易想到答案的。下面就是我的解法:

ListNode* swapPairs(ListNode* head) {
    ListNode preHead(0);
    preHead.next = head;
    ListNode* p0 = &preHead;
    ListNode* p1 = p0->next;
    ListNode* p2 = p1 ? p1->next : NULL;
    while (p1 && p2) {
	p0->next = p2;
	p1->next = p2->next;
	p2->next = p1;

	p0 = p1;
	p1 = p0->next;
	p2 = p1 ? p1->next : NULL;
    }
    return preHead.next;
}

Approach 2 recursive

这道题的另一种解法是使用递归，这种解法能够完成题目中要求的节点交换操作。不过需要注意的是递归会使用额外的空间，所以并不能满足题目中要求的常数空间复杂度。

void helper(ListNode* preHead){
    ListNode* p1 = preHead->next;
    ListNode* p2 = p1 ? p1->next : NULL;
    if (!p1 || !p2) {
	return;
    }

    preHead->next = p2;
    p1->next = p2->next;
    p2->next = p1;

    helper(p1);
}

ListNode* swapPairs(ListNode* head) {
    ListNode preHead(0);
    preHead.next = head;
    helper(&preHead);
    return preHead.next;
}