LeetCode-24-两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

准备工作

定义链表结点：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

数组转链表，方便测试数据的输入：

function arrayToList(array) {
    let node = null;
    for (let i = array.length - 1; i >= 0; i --) {
        let newNode = new ListNode(array[i]);
        newNode.next = node;
        node = newNode;
    }
    return node;
}

链表转字符串，方便测试结果的显示：

function listToString(node) {
    return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}

解答

每两个结点进行一次交换，具体的实现如下：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs1 = function(head) {
    let prevHead = new ListNode(null); // 单独的头结点
    prevHead.next = head;
    let node = prevHead; // 指向要交换的两个结点之前的结点
    let temp; // 临时变量
    while (node.next && node.next.next) { // 还剩2个结点才交换
        temp = node.next.next.next; // 用临时变量保存结点二的next
        node.next.next.next = node.next; // 结点二的next指向结点一
        node.next = node.next.next; // node的next指向结点二
        node.next.next.next = temp; // 原结点一的next指向临时变量
        node = node.next.next; // node后移两次
    }
    return prevHead.next;
};

测试：

let start = new Date();
const test = swapPairs1;
console.log(listToString(test(arrayToList([1, 2, 3, 4])))); // 2 -> 1 -> 4 -> 3
console.log(new Date().getTime() - start.getTime()); // 3

时间复杂度： 一次遍历，时间复杂度为O(n)
空间复杂度： 常数级的额外空间，空间复杂度为O(1)

本文由 李海平 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 30,2019