上回说到面试中的一个高频题目：单链表反转，提到它的“难兄难弟”不是那么简略。明天就来剖析一下它的二哥：“两两替换链表中的节点”。
题目形容如下。
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。
你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。
示例:
给定 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 个一组翻转链表