No.24 两两交换链表中的结点 （Medium）

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

思路

该题可以有递归解法和非递归解法，将两个结点看成一组，让head指向一组结点中的第一个结点，那么整个过程就是：

1. head的下一个结点指向head；
2. head结点指向下一组交换好了的结点。

递归

使用递归时，不要尝试考虑模拟调用栈，进入递归。而要理解递归的三个要素：

1. 终止条件；
2. 单次运行的逻辑；
3. 返回值。

在本题中：

1. 终止条件即head == null 或者 head.next ==null , head == null 表示最后已经没有结点了， head.next == null则表示最后一组结点中仅包含一个结点，无法进行交换
2. 单次运行的逻辑中，第一步将head的下一个结点指向head, 第二步将head指向下一组交换好的结点；
3. 返回值是交换完成以后的第一个结点。

递归代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            // 不能返回空，
            // 因为当head.next == null时，表示最后剩一个结点，要把该结点返回回去进行连接。
            return head;
        }
        // 保存第二个结点
        ListNode nextNode = head.next;
        // 保存下一组结点的开始结点
        ListNode nextHead = nextNode.next;
        // 第二个结点指向第一个结点
        nextNode.next = head;
        // 第一个结点指向交换完成后的下一组结点的第一个结点
        head.next = swapPairs(nextHead);
        // 返回第二个结点（因为在交换后，会变成第一个结点）
        return nextNode;
    }
}

优化：在上面的代码中，时间击败了100%， 但是内存仅击败了7.1%， 这是因为我们首先改变了第二个结点的指向，导致需要用额外的变量nextHead来保存下一组结点的开始结点。因此我们把逻辑顺序交换一下：

1. head结点指向下一组交换好了的结点。
2. head结点的下一个结点指向head.

那么代码变成：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            // 不能返回空，
            // 因为当head.next == null时，表示最后剩一个结点，要把该结点返回回去进行连接。
            return head;
        }
        // 保存第二个结点
        ListNode nextNode = head.next;
        // 第一个结点指向交换完成后的下一组结点的第一个结点
        head.next = swapPairs(nextNode.next);
        // 第二个结点指向第一个结点
        nextNode.next = head;
        // 返回第二个结点（因为在交换后，会变成第一个结点）
        return nextNode;
    }
}

此时空间得到优化。

非递归

在非递归的过程中，要用到循环遍历，在一次循环中以下两步很容易实现：

1. 第二个结点指向第一个结点，即1 -> 2变成 2-> 1;
2. 第一个结点指向下一组未交换的结点，即2->1->3->4;

但是，我们期望的是得到2->1->4->3，因此需要在完成交换后，记录下来第一个结点，在下一次循环中让第一个结点指向下一组结点的第二个结点（而非第一个结点），即实现2->1->3->4 到 2->1->4->3的转化。

因此，在代码中我们使用一个temp来存储第一个结点。

非递归代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 记住temp的定义，上一组结点的最后一个结点，
        // 也就是说对于2->1->3->4, 遍历到结点3和4的时候，temp指向的是1
        ListNode temp = dummy;
        // 该条件表示只有存在两个结点时，才能进行循环
        // 不能只用temp.next.next != null 来判断，因为可能temp.next已经等于null了
        // 那么temp.next.next会报错，空指针异常
        while (temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            // 在第一次循环中，temp.next指向了2, 因为temp = dummy, 所以dummy.next也指向了2
            // 那么最后返回dummy.next也就是2，即新的头结点
            // 在第二次循环中，因为代码temp = start， 即temp指向了1
            // temp.next = end 使得 1 指向了4， 即完成了2->1->3->4变成2->1->4->3的转变
            temp.next = end;
            // 1 -> 3
            start.next = end.next;
            // 2 -> 1
            // 完成后变成2->1->3->4
            end.next = start;
            // 用temp来保存1
            temp = start;
        }
        return dummy.next;
    }
}

可以发现，非递归的代码比递归代码复杂，也不好理解，因此推荐使用递归解决该问题。