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

[swiftwind0405]

方法一：递归

解题思路：
可以定义一个递归的辅助函数 helper，这个辅助函数对于节点和它的下一个节点进行交换，比如 helper(1) 处理 1 -> 2，并且把交换变成 2 -> 1 的尾节点 1 的 next 继续指向 helper(3) 也就是交换后的 4 -> 3。
边界情况在于，如果顺利的作了两两交换，那么交换后我们的函数返回出去的是 交换后的头部节点，但是如果是奇数剩余项的情况下，没办法做交换，那就需要直接返回 原本的头部节点。

代码：

var swapPairs = function(head) {
    if (!head) return null;
    function helper(node) {
        let tempNext = node.next;
        if (tempNext) {
            let tempNextNext = node.next.next;
            node.next.next = node;
            node.next = tempNextNext ? helper(tempNextNext) : null;
        }

         return tempNext || node
    }

    return helper(head) || head;
};

用自身进行递归的代码：

var swapPairs = function(head) {
     // 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了
    if (head == null || head.next == null) return head;

    // 2. 调用单元
    // 需要交换的两个节点是 head 和 head.next
    let firstNode = head;
    let secondNode = head.next;
    // firstNode 连接后面交换完成的子链表
    firstNode.next = swapPairs(secondNode.next);
    // secondNode 连接 firstNode
    secondNode.next = firstNode;

    // 3. 返回值：返回交换完成的子链表
    // secondNode 变成了头结点
    return secondNode;
};

复杂度分析：

• 时间复杂度：O(N)，N 指的是链表的节点数量。
• 空间复杂度：O(N)，递归过程使用的堆栈空间。

方法二：循环

加哨兵节点

代码：

var swapPairs = function(head) {
    let shaob = new ListNode(0); // 添加哨兵 加0
    shaob.next = head;
    let shao = shaob;   //shao 是为了一直往下指, 而 shaob 其实是为了返回第二个节点
    while(shao.next != null && shao.next.next != null) {
        let start = shao.next; // 代表第一次的1
        let end = shao.next.next; // 代表第一次的2
        shao.next = end; // 0 指向 2
        start.next = end.next; // 1 指向 3
        end.next = start; // 2 指向 1
        shao = start; // 将此时的1 也就是交换后的1当哨兵 继续循环
    }
    return shaob.next // 返回的是最初哨兵的前一个 就是链表头
};

复杂度分析：

• 时间复杂度：O(N)，N 指的是链表的节点数量。
• 空间复杂度：O(1)。