一、题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]示例 2：
输入：head = []
输出：[]示例 3：
输入：head = [1]
输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/swap-nodes-in-pairs
二、题解
想要交换结点 A 和结点 B（假设 A 在 B 之前），需要一个指针 cur 指向结点 A 的前一个结点，才能完成交换操作
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
初始时，要交换第一个结点和第二个结点，所以先定义一个指针 cur 指向虚拟头结点
具体交换步骤：
- 让结点 B 成为 cur 的下一个结点
- 让结点 A 成为 结点 B 的下一个结点
- 让结点 B 的下一个结点成为结点 A 的下一个结点
结合图示更好理解：
需要注意的是，进行步骤一之前，要先用一个临时指针保存结点 1 的地址，否则进行步骤二时找不到结点 1。
同理，进行步骤二之前，要先用一个临时指针保存结点 3 的地址，否则进行步骤三时找不到结点 3。
交换完成后，再移动 cur，进行下一轮交换
这道题目的关键之处就是用 cur 遍历链表时终止条件一定要想清楚
如果链表节点数量为偶数，则 current.next 为空时遍历结束
如果链表节点数量为奇数，则 current.next.next 为空时遍历结束
两个条件不能反过来写，否则容易发生空指针异常
三、代码
public class T24 {
//非递归版本
public ListNode swapPairs(ListNode head) {
// 设置一个虚拟头结点
ListNode dummyHead = new ListNode();
// 将虚拟头结点指向head，这样方面后面做删除操作
dummyHead.next = head;
ListNode cur = dummyHead;
while (cur.next!=null && cur.next.next!=null){
ListNode tmp = cur.next;//记录临时节点，保存两个节点之中的第一个节点
ListNode tmp1 = cur.next.next.next;//记录临时节点，保存两个节点后面的节点
cur.next = cur.next.next;
cur.next.next = tmp;
cur.next.next.next = tmp1;
//cur移动两位，准备下一轮交换
cur = cur.next.next;
}
return dummyHead.next;
}
//递归版本
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null){
return head;
}
// 获取当前节点的下一个节点
ListNode nextNode = head.next;
// 进行递归
ListNode newNode = swapPairs(nextNode.next);
// 交换节点
nextNode.next = head;
head.next = newNode;
return nextNode;
}
private class ListNode{
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}