重启数据结构与算法2

[Ray-56]

重启数据结构与算法2

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2

单向链表的五个面试题

这几个题，就直接在HeroNode类中写了，查看上篇重启数据结构与算法1

1.求单链表中的有效的节点个数

class SingleLinkedList {
    ...
    /** 获取当前单链表 */
    public getHead() {
        return this.head;
    }
    /** 有效节点数 */
    public static getSize(head: HeroNode): number {
        let size = 0;
        let cur = head;
        while (cur.next) {
            size++;
            cur = cur.next;
        }
        return size;
    }
}

定义了getSize(head)静态方法，参数为要获取有效节点的单链表
再定义getHead()方法，获取当前的链表

下面我们验证一下

// 提前已将节点加入进去了
// 验证获取有效节点数量
const size = SingleLinkedList.getSize(singleLinkedList.getHead());
console.log(`有效节点数量为：${size}`);
// 有效节点数量为：4

2.查找单链表倒数第k个节点

...
/** 查找倒数第k个节点 */
public static findLastIndexNode(head: HeroNode, index: number) {
    const size = this.getSize(head);
    // if (index <=0 || index > size) return null;
    let ret  = head;
    for (let i = 0; i < size - index; i++) {
        ret = ret.next as HeroNode;
    }
    return ret;
}
...

window.onload = function main() {
    ...
    // 验证查找倒数第k个节点
    const lastNode = SingleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 2);
    console.log(`倒数第3个节点为：`);
    lastNode.show();
    // 倒数第3个节点为：
    // no = 2; name = 卢俊义; nickName = 玉麒麟
}

添加findLastIndexNode方法后进行了验证，也没有问题

3.单链表反转

反转要比前面有点难度了，前面只需要遍历次数就可以，现在要考虑数据结构的转变方向了

...
    /** 反转 */
    public static reverseList(head: HeroNode) {
        // 思路1 保存上一个，使得当前的下一个是上一个，pre 即为反转后的链表
        // let cur: HeroNode | null = head;
        // let pre = null;
        // while (cur !== null) {
        //     const next: HeroNode | null = cur.next;
        //     cur.next = pre;
        //     pre = cur;
        //     cur = next;
        // }
        // return pre;

        // 思路2 新建链表，遍历旧的使得每一个都放在新链表下的第一位
        const reverseHead = new HeroNode(0, '', '');
        let cur: HeroNode | null = head;
        while (cur !== null) {

            const next: HeroNode | null = cur.next; // 保存 next

            // 保证当前的一直在 reverseHead.next
            cur.next = reverseHead.next;
            reverseHead.next = cur;

            cur = next;
        }
        head.next = reverseHead.next;
    }
...

window.onload = function main() {
    ...
    // 验证反转
    const head = singleLinkedList.getHead();
    SingleLinkedList.reverseList(head);
    console.log(head); // 输出得知已被反转
}

4.从尾到头打印链表

• 可以是考虑反转后再打印，这样要考虑当前链表是否需要被反转，否则转过来再转过去损耗性能
• 使用栈stack先进后出的特性

...
    /** 从尾到头打印链表 */
    public static reversePrint(head: HeroNode) {
        const stack = [];
        let cur = head;
        while (cur.next) {
            cur = cur.next;
            stack.push(cur);
        }

        while (stack.length) {
            stack.pop()?.show();
        }
    }
...

window.onload = function main() {
    ...
    // 验证从尾到头打印
    const head = singleLinkedList.getHead();
    SingleLinkedList.reversePrint(head);
}

5.合并有序单链表，合并后依然有序

...
    /** 合并有序单链表，合并后依然有序 */
    public static merge(l1: HeroNode | null, l2: HeroNode | null): HeroNode {
        let cur = new HeroNode(0, '', '');
        const ret = cur;

        while (l1 !== null && l2 !== null) {
            if (l1.no < l2.no) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 !== null) {
            cur.next = l1;
        }
        if (l2 !== null) {
            cur.next = l2
        }

        return ret.next as HeroNode;
    }
...

window.onload = function main() {
    ...
    // 验证合并有序单链表，合并后依然有序
    const singleLinkedList1 = new SingleLinkedList();
    const singleLinkedList2 = new SingleLinkedList();
    singleLinkedList1.add(hero1);
    singleLinkedList1.add(hero3);
    singleLinkedList2.add(hero2);
    singleLinkedList2.add(hero4);
    console.log('链表1：');
    singleLinkedList1.show();
    console.log('链表2：');
    singleLinkedList2.show();

    const merged = SingleLinkedList.merge(singleLinkedList1.getHead().next, singleLinkedList2.getHead().next);
    console.log('合并后的有序：');
    console.log(merged); // 验证后依然有序
}

下期预告

双向链表、环形链表以及约瑟夫问题