P24. 两两交换链表中的节点

## 题目给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

迭代

使用哑节点d简化头节点处理

通过prev指针维护已处理部分与待处理部分的连接

每次取两个节点first和second进行交换

交换完成后更新prev位置继续下一轮

public ListNode swapPairs(ListNode head) {
    if(head==null||head.next==null){
        return head;
    }
    ListNode d=new ListNode(0);
    d.next=head;
    ListNode prev=d;

    while (prev.next!=null&&prev.next.next!=null){
        ListNode first=prev.next;
        ListNode second=prev.next.next;

        first.next=second.next;
        second.next=first;
        prev.next=second;

        prev=first;
    }

    return d.next;
}

方面	迭代	递归
空间复杂度	O(1)	O(n)
理解难度	稍复杂(需维护多个指针)	较简单(分治思想)
实现方式	显式循环控制	函数调用栈

将问题分解为:处理前两个节点 + 递归处理剩余链表
tmp保存第二个节点，作为新的头节点
递归处理tmp.next之后的链表
重新连接当前两个节点的指向关系

关键差异

递归

将问题分解为:处理前两个节点 + 递归处理剩余链表

tmp保存第二个节点，作为新的头节点

递归处理tmp.next之后的链表

重新连接当前两个节点的指向关系

public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
    return head;
}
// 假设1 2 3 4
// 存储当前的head.next 也就是保存两个量在一层  1和2 3和4
ListNode tmp=head.next;
// 直接跳到3,等3和4处理完成然后1去连接
head.next = swapPairs(tmp.next);
// 最后4连接3
tmp.next=head;
return tmp;
}