24. 两两交换链表中的节点
24. 两两交换链表中的节点
分析
交换链表中的两个点，实际上涉及到四个点
即，我们要交换 AB 两个节点，实际上涉及到 前、A、B、后四个节点，其中要求改的为 前、A、B 三个节点。
而 AB 这两个节点其实也可以通过最前面那个节点的 next 指针访问到，于是思路就有了，用 while 循环，一次循环交换两个节点，交换完成后往后走两个节点，如果后面不足两个节点，就跳出来，这就是大概的思路。
在循环中设置下一此交换的头结点的时候，很容易搞错，因为节点的指针已经更换了，一个万无一失的办法就是从当前循环的 nowNode 通过 next 来访问 nowNode.next.next。
解题
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode nowNode = dummyHead;
//两两一组,同时这一组的前一个节点为当前节点
while (nowNode != null && nowNode.next != null && nowNode.next.next != null) {
ListNode eleOne = nowNode.next;
ListNode eleTwo = eleOne.next;
// 交换之前，先把最终节点找到
ListNode end = eleTwo.next;
// 开始交换
nowNode.next = eleTwo;
eleTwo.next = eleOne;
eleOne.next = end;
//调整后,下一次循环的起点
nowNode = eleOne;
// 或者你也可以从最新的 nowNode 开始找
// nowNode = nowNode.next.next;
}
return dummyHead.next;
}
更高级的方法，用递归，递归的思路先交换后面的，再交换前面的，交换交换完后面的，
假设一开始是 A-B-C-D，最后一次交换，先交换 C 和 D，并最终返回 D，然后倒数第二次交换，直接设置 A 的下一个节点为 D，然后 B 的下一个节点是 A，最终返回 B，结果就是 B-A-D-C，
非常短小精妙，当然写起来也更容易写错。哈哈哈
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 一开始就可以确定这一次递归要返回的元素，
ListNode newHead = head.next;
// 第一个元素的下一个元素为下一对要交换的元素的第二个元素，也就是下一对元素交换之后的排在前面的元素
// 这一句是整个递归的精髓
head.next = swapPairs(newHead.next);
// 让这一对的第二个元素指向这一对的第一个元素
newHead.next = head;
// 返回这一对的第二个元素
return newHead;
}