这是笔者面试某司的一道算法题,感觉还是挺不错的题,然后把自己的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)}`);