链表找头节点并判断链表环状,以及节点不在链表内等异常情况

这是笔者面试某司的一道算法题,感觉还是挺不错的题,然后把自己的js解题代码公布了出来欢迎大家一起交流看看哪里有改进的空间~

问题:

寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。

PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常消息即可。

const findFirstNode = (nodeList) => {
	// 存放有可能是链头的数组
    const startArr = [];
    // 存放有可能是链尾的数组
    const endArr = [];
    // 循环每个节点并找到他的上一个节点与下一个节点
    nodeList.forEach(ite => {
        let nextItem, preItem;
        nodeList.some(i => {
            if (i.id === ite.nextId) {
                nextItem = i;
            } else if (i.nextId === ite.id) {
                preItem = i;
            }
            return nextItem && preItem;
        });
        if (!nextItem) endArr.push(ite);
        if (!preItem) startArr.push(ite);
    });
    if (startArr.length >= 2) return console.error('链表出现了中断');
    if (!startArr.length || !endArr.length) return console.error('这可能是一个环表');
    return startArr[0].id;
}
const list = [{"id":3,"nextId":1},{"id":1,"nextId":2},{"id":2,"nextId":3}];
console.log(`结果: ${findFirstNode(list)}`);

 

上一篇:# EA 的练习赛 2 题解


下一篇:PAT 1009