这道js链表分组的问题怎么做？

Question

给定一个数组，数组记录了当前数据的ID，和后面紧邻的数据ID。对该数据进行分组，实现以下功能:
功能描述:
对数组进行分类，
如果当前数据没有被其他数据的next指向，则为一个数组的第一个数据，
如果当前数据有被其他数据的next指向，则排在next指向的后面，
其他以此类推。
const data = [

{ id: 1, next: 2 },
{ id: 3, next: 4 },
{ id: 4, next: 5 },
{ id: 5, next: 6 },
{ id: 6, next: 7 },
{ id: 7, next: 8 },
{ id: 8, next: 9 },
{ id: 2, next: 10 },
{ id: 20, next: 30 },
{ id: 30, next: 40 },
{ id: 100, next: 78 }

]

getLinks(data)
=>
[

[{ id: 1, next: 2 }, { id: 2, next: 10 }],
[{ id: 3, next: 4 }, { id: 4, next: 5 }, { id: 5, next: 6 }, { id: 6, next: 7 }, { id: 7, next: 8 }, { id: 8, next: 9 }]
[{ id: 20, next: 30 }, { id: 30, next: 40 }],
[{ id: 100, next: 78 }]

]

Answer 1

提供思路，哈希表 新建 {"id":"newxt" } 的 js object 。{1:2,2:10,3:4...}
循环取出来就行

Answer 2

首先满足的是下面的数组结构 [[{},{}],[{},{}]] ，这就意味你需要新建一个listArr去存储list，再用新建的list去存obj。明白这个数据结构后就是应该如何提取数据。

可以先将原始数据按照id排序，新建一个变量dataCheck存储原始数组data，用于提取数据。

从id==1的开始循环，把id==1从dataCheck里面提取出来，存进list1里，进入dataCheck里循环找到id==next的对象，没找到就新建list2，把id==2的抓出来找，循环下一个。找到就替换id==1的位置，接着找，直到找不到，启动list2，把list1存到listArr里面。

不给代码给思路，你琢磨一下（要下班吃饭了。

Answer 3

function getLinks(data) {
    data = Object.fromEntries(data.map(i => [i.id, {obj: i}]));
    Object.entries(data).forEach(([k, v]) => (data[v.obj.next] ?? {}).prev = k);
    return Object.values(data).filter(i => !('prev' in i)).map(i => {
        let arr = [];
        do {
            arr.push(i.obj);
        } while (i = data[i.obj.next]);
        return arr;
    });
}

Answer 4

let idList = [] // id集合
let nextList = [] // next集合
data.forEach(({id, next}) => {
    idList.push(id)
    nextList.push(next)
})
let list = data.filter(v => !nextList.includes(v.id)).map(v => {
    let obj = v
    let arr = []
    while (obj) {
      arr.push(obj)
      obj = data[idList.indexOf(arr[arr.length - 1].next)]
    }
    return arr
})

Answer 5

function getLinks(data) {
    const links = new Map();
    const groups = [];

    data.forEach((item) => {
        const { id, next } = item;
        links.set(id, next);
    });

    while (links.size > 0) {
        let currentId = null;

        for (const [id, nextId] of links) {
            if (!links.has(nextId)) {
                currentId = id;
                break;
            }
        }

        if (currentId === null) {
            for (const [id, nextId] of links) {
                currentId = id;
                break;
            }
        }

        const group = [];
        let nextId = links.get(currentId);

        while (nextId) {
            group.push({ id: currentId, next: nextId });
            links.delete(currentId);
            currentId = nextId;
            nextId = links.get(currentId);
        }

        group.push({ id: currentId, next: null });
        links.delete(currentId);
        groups.push(group);
    }

    return groups;
}

getLinks(data)
=>
[
  [{ id: 1, next: 2 }, { id: 2, next: 10 }],
  [{ id: 3, next: 4 }, { id: 4, next: 5 }, { id: 5, next: 6 }, { id: 6, next: 7 }, { id: 7, next: 8 }, { id: 8, next: 9 }],
  [{ id: 20, next: 30 }, { id: 30, next: 40 }],
  [{ id: 100, next: 78 }]
]

Answer 6

function getLinks(data) {
    if(!data.length) return []; 
    const result = [[data.shift()]];
    while(data.length) {
        const prev = result[result.length-1];
        const node = prev[prev.length-1];
        const index = data.findIndex(v => v.id == node.next)
        if(index > -1) prev.push(data.splice(index,1)[0])
        else result.push([data.shift()])
    }
    return result
}

上面代码可优化，findIndex嵌套在while里是可优化的，数据量不大可不考虑