剑指offer - 反转链表 - JavaScript

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

题目描述

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

解法 1: 借助栈

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

处理过程如下:

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

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

// ac地址:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
// 原文地址:https://xxoo521.com/2020-01-12-reverse-link/
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) {
        return null;
    }

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

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

解法 2: 原地反转

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

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

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

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

// ac地址:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
// 原文地址:https://xxoo521.com/2020-01-12-reverse-link/
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) {
        return null;
    }

    let node = head;
    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

×