从尾到头打印链表

1. 题目描述

输入一个链表，从尾到头打印链表每个节点的值。

2. 解题思路

可以从头到尾遍历一遍链表，将节点放入栈中，然后依次取出打印（后入先出）。

优化就是借助“递归”，先向下查找再打印输出，也可实现这种“后入先出”。可以类比二叉树的后序遍历。

3. 代码

用 JS 实现了简单实现了链表这种数据结构，这不是重点。

重点在printFromTailToHead函数。

class Node {
    /**
     * 节点构造函数
     * @param {*} value
     * @param {Node} next
     */
    constructor(value, next) {
        this.value = value;
        this.next = next;
    }
}

class List {
    constructor() {
        this.head = new Node(null, null);
    }

    /**
     * 从0开始计算，找到包括head在内的位于index的节点
     * @param {Number} index
     */
    find(index) {
        let current = this.head;
        for (let i = 0; i < index; ++i) {
            current = current.next;
        }
        return current;
    }

    /**
     * 向index位置插入元素
     * @param {*} value
     * @param {Number} index
     */
    insert(value, index) {
        const prev = this.find(index);
        const next = new Node(value, prev.next);
        prev.next = next;
    }
}

/**
 * 逆序打印链表
 * @param {Node} node
 */
function printFromTailToHead(node) {
    if (node.next) {
        printFromTailToHead(node.next);
    }
    node.value && console.log(node.value);
}

/**
 * 以下是测试代码
 */
let list = new List();
list.insert("a", 0);
list.insert("b", 1);
list.insert("c", 2);

printFromTailToHead(list.head);

快速删除链表节点

1. 题目描述

给定单向链表的头指针和一个结点指针，定义一个函数在 $O(1)$ 时间删除该结点。

2. 思路描述

正常的做法肯定是在 $O(N)$ 时间内删除节点。而这么过分的要求，显然是通过“重新赋值”才能做到。

比如要删除节点 a，那么就将 a.next 的 value 和 next 赋值给节点 a，然后删除 a.next。

表面“看起来”像是删除了节点 a，其实是将其后节点的信息转移到了它自己身上。

除此之外，对于最后一个节点，还是要退化成 $O(N)$ 的复杂度。而整体分析一下复杂度：

$$ O(T) = (O(N) + O(1) * (n - 1)) / n = O(1) $$