剑指offer - 反转链表 - JavaScript

题目描述:输入一个链表,反转链表后,输出新链表的表头。

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章,获得更好阅读体验

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解法 1: 借助栈

借助栈的后入先出的顺序,可以将顺序列表逆序。不过这不是原地反转,当然题目也没有要求。

处理过程如下:

  • 从头到尾遍历链表,将节点 val 依次放入栈
  • 从栈中依次取出 val,构造新节点,并连接节点

时间复杂度 O(N),空间复杂度 O(N)。代码如下:

// 原文地址:https://xxoo521.com/2020-01-12-reverse-link/
// ac地址:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

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

function ReverseList(pHead) {
    if (!pHead) {
        return null;
    }

    const stack = [];
    let node = pHead;
    while (node) {
        stack.push(node.val);
        node = node.next;
    }

    const head = {
        val: stack.pop(),
        next: null
    };
    node = head;
    while (stack.length) {
        node.next = {
            val: stack.pop(),
            next: null
        };
        node = node.next;
    }
    return head;
}

解法 2: 原地反转

“原地反转”的思路简单,但是实现起来有一些细节需要处理。链表类的原地操作,大部分都是细节上容易出错,导致死循环或者报错。

准备当前节点 node,和 node 的前一个节点 preNode。整体的思路如下:

  • 保留当前节点的下一个节点
  • 将当前节点的 next 指向前一节点 preNode
  • 更新 preNode 为当前节点,更新当前节点为第一步保留的下一节点
  • 判断当前节点是否是最后节点,如果不是,回到第一步;如果是,进入最后一步
  • 将当前节点的 next 指向前一节点 preNode

时间复杂度是 O(N),空间复杂度是 O(1)。代码如下:

// 原文地址:https://xxoo521.com/2020-01-12-reverse-link/
// ac地址:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

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

function ReverseList(pHead) {
    if (!pHead) {
        return null;
    }

    let node = pHead;
    let preNode = null;
    while (node.next) {
        const nextNode = node.next;
        node.next = preNode;
        preNode = node;
        node = nextNode;
    }
    node.next = preNode;
    return node;
}
# ,

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×