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

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

题解

递归解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：39.2 MB, 在所有 Java 提交中击败了21.37%的用户

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归终止：如果只有一个节点|奇数节点|偶数节点，已经交换完成
        if (head == null || head.next == null) return head;
        // 存放下一个节点
        ListNode next = head.next;
        // 下一对交换返回的头节点
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

迭代解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：39.3 MB, 在所有 Java 提交中击败了9.38%的用户

// 使用 pre 存放前置节点，n1 存放 pre 的下个节点，n2 存放 pre 的下下个节点
// 每次遍历都交换 n1 和 n2 的位置
// 由于第一个节点没有前置节点，所以自己创建一个节点作为 head 的前置节点
// 遍历终于条件是 pre 的下个和下下个节点都不为空。
// 为什么遍历终止条件要求 pre 下下节点不为空？因为链表长度为奇数时最后一个节点不需要交换
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode pre = temp;
        while(pre.next != null && pre.next.next != null) {
            ListNode n1 = pre.next;
            ListNode n2 = pre.next.next;
            n1.next = n2.next;
            n2.next = n1;
            pre.next = n2;
            pre = n1;
        }
        return temp.next;
    }
}