LeetCode 24. Swap Nodes in Pairs

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

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
解析：
给定一个链表，交换两个相邻节点，并返回头节点。要求使用常数空间，并且只能交换节点不可以更改数值。
方法1:
采用递归方式，实际上利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换。
[cc lang=”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 || head->next ==NULL)
return head;
ListNode* temp = head->next;
head->next = swapPairs(temp->next);
temp->next = head;
return temp;
}
};
[/cc]
该方法中，依次执行到链表结尾，然后head->next == NULL,temp指向head，此过程实现了交换最后的两个节点，并把倒数第二个节点返回，继续回溯，依次往前交换节点。
方法2:
迭代实现，对于迭代实现，还是需要建立dummy节点。
[cc lang=”C++”]
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;
}
[/cc]
迭代实现，执行时间更短一点。

此题目在迭代过程中，需要两个指针pre,t，其中pre指向要处理的两个节点的前驱，t指向两个节点的末尾一个，并且保证在处理的过程中，链表不会断裂。
参考：https://www.cnblogs.com/grandyang/p/4441680.html