上回说到面试中的一个高频题目：单链表反转，提到它的“难兄难弟”不是那么简略。明天就来剖析一下它的二哥：“两两替换链表中的节点”。
题目形容如下。
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。
你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
办法一：三指针迭代
有了上回单链表反转的双指针迭代法的根底，再来解决它二哥，就绝对容易很多了。
“巧妇难为无米之炊”。题目中说的是要两两替换，那首先得有两个节点才行，所以上来先判断够两个节点才持续替换，而且循环持续的条件也是要满足剩下的节点够两个才行。
咱们能够应用两个变量first和second来示意以后要进行替换的第一个节点和第二个节点。
如上图，替换后，2nd节点指向1st节点，而1st节点不能再指向2nd节点了，否则就造成了环。应该让1st节点指向2nd节点原来的下一个节点，所以咱们须要当时把2nd节点原来的下一节点记录下来。
替换操作伪代码如下：
ListNode third = second.next;second.next = first;first.next = third;同时，要思考上面的这种场景，节点1和节点2曾经实现替换，当初轮到节点3和节点4的替换，要保障节点3和节点4替换后，节点1指向的是节点4，所以还要记录每一轮替换的前驱节点，下图这个例子外面前驱节点就是节点1。
最初要返回的头指针为第一轮替换中的第二个节点。
动画演示如下。
class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = null, first = head, second = head.next; ListNode ans = second; while (first != null && second != null) { ListNode third = second.next; second.next = first; first.next = third; // 记录前驱节点 if (pre != null) { pre.next = second; } pre = first; // 1st，2nd 向前走 first = third; second = (first != null) ? first.next : null; } return ans; }}复杂度剖析
- 工夫复杂度：
O(n)。 - 空间复杂度：
O(1)。
办法二：递归
上回说到的递归的时候，我写了一段本人都递归的感悟，这里忍不住再写一遍。
递归是个神奇的存在，那么简略，又那么简单，有时感觉它很近，实际上它却那么远，有时感觉重新认识了它，可它还是那个它，从未扭转过。每一次应用递归，都会对它了解更深一点。
如果把替换两个节点看做一个回合的话，那么两两替换链表中的所有节点是由很多这样的回合组成。递归是要倒着来的，就是说咱们在进行以后回合的替换的时候，能够假设未来的回合曾经实现了。
如下示意图所示，还拿链表1->2->3->4->5->null来举例，在进行节点1和节点2的替换的时候，假设3->4->5->null曾经实现了替换，节点1指向swapPairs(3)返回的节点：
代码如下：
class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode first = head, second = head.next; first.next = swapPairs(second.next); second.next = first; return second; }}复杂度剖析
- 工夫复杂度：
O(n)。 - 空间复杂度：
O(n)，应用了递归，递归的栈深度为n。
下集预报，单链表反转的“大哥”：
- K 个一组翻转链表