王鹏飞

Blog

Tutorial

About

算法与数学

2021年4月12日

从尾到头打印链表

单链表的方向是单向的,如果要获得某个结点,必须从头结点开始向尾部查询,直到找到该结点。所以如果题目是从头到尾打印链表,那么就很简单,只需要从头结点依次循环打印即可。

一. 思路

我们可以利用栈的后进先出的特性,来解决这个题目。还是从头结点遍历,每到一个结点,将该结点的值存储到数组中,直至遍历完整个链表。最后我们得到了一个按顺序存储结点值得数组。我们只需要从尾部开始向头部遍历数组,即可打印出正确的结果,这就是典型的后进先出的应用。

二. 解题

根据上面的思路,很容易的写出如下代码:

// 链表的结点类
class ListNode {
    public value: number | null;
    public next: ListNode | null;
    constructor(value, next) {
        this.value = value;
        this.next = next;
    }
}
// 创建一个链表
const createLinkList = (values: number[]) => {
    const head = new ListNode(null, null);
    let preNode = head;
    for (let i = 0; i < values.length; i++) {
        const currentNode = new ListNode(values[i], null);
        preNode.next = currentNode;
        preNode = currentNode;
    }
    return head;
};
/**
 * 利用栈的后进先出的特点,从尾到头打印链表
 */
const printLinkReverse = (head: ListNode) => {
    const values: number[] = [];
    let curNode = head.next;
    while(curNode) {
        values.push(curNode.value);
        curNode = curNode.next;
    }
    for (let i = values.length - 1; i >= 0; i--) {
        console.log(values[i]);
    }
};
// 测试
const arr1 = [1, 2, 3, 4, 5, 6];
const arr2 = [-1, -3, -10, 10, -1, 3];
const arr3 = [];
console.log(arr1);
printLinkReverse(createLinkList(arr1));
console.log(arr2);
printLinkReverse(createLinkList(arr2));
console.log(arr3);
printLinkReverse(createLinkList(arr3));

首先,我手动构建了链表结构,实际解决代码是printLinkReverse,最后我添加了测试代码。

(完)

数组—二维数组中的查找
二叉树—已知二叉树的前序遍历和中序遍历,输出二叉树

留言(0


发表评论

邮箱地址不会被公开。*表示必填项