Cho mảng object đại diện các trang web, mỗi object có next (trừ trang cuối) và previous (trừ trang đầu) trỏ đến id của object khác. Mảng đang random, cần sắp xếp đúng thứ tự.
Dữ liệu
let arr = [ { id: "1325asdfasdasd", next: "5345341fgdfgdd", previous:"545234123fsdfd" }, { id: "das987as9dya8s", next: "3j12k3b1231jkj" }, { id: "89ad8sasds9d8s", previous: "1j3b12k3jbasdd" }, { id: "5345341fgdfgdd", next: "1j3b12k3jbasdd", previous:"1325asdfasdasd" }, { id: "1423123123asfd", next: "545234123fsdfd", previous:"3j12k3b1231jkj" }, { id: "1j3b12k3jbasdd", next: "89ad8sasds9d8s", previous:"5345341fgdfgdd" }, { id: "3j12k3b1231jkj", next: "1423123123asfd", previous:"das987as9dya8s" }, { id: "545234123fsdfd", next: "1325asdfasdasd", previous:"1423123123asfd" }, ];
Giải pháp 2 bước
Bước 1: Tạo Map id→object, tìm object đầu (không có previous).
const objectMap = new Map(); let firstObject; const sortedArray = []; for(const obj of arr){ objectMap.set(obj.id, obj); if(!obj.previous){ firstObject = obj; } }
Bước 2: Duyệt theo chuỗi next từ firstObject, push vào sortedArray.
for(let start = firstObject; start; start = objectMap.get(start.next)){ sortedArray.push(start); } console.log(sortedArray);
Kết quả
Mảng đã sắp xếp đúng thứ tự liên kết (linked list):
[ { id: 'das987as9dya8s', next: '3j12k3b1231jkj' }, { id: '3j12k3b1231jkj', next: '1423123123asfd', previous: 'das987as9dya8s' }, { id: '1423123123asfd', next: '545234123fsdfd', previous: '3j12k3b1231jkj' }, { id: '545234123fsdfd', next: '1325asdfasdasd', previous: '1423123123asfd' }, { id: '1325asdfasdasd', next: '5345341fgdfgdd', previous: '545234123fsdfd' }, { id: '5345341fgdfgdd', next: '1j3b12k3jbasdd', previous: '1325asdfasdasd' }, { id: '1j3b12k3jbasdd', next: '89ad8sasds9d8s', previous: '5345341fgdfgdd' }, { id: '89ad8sasds9d8s', previous: '1j3b12k3jbasdd' } ]
O(n) time, O(n) space. Map cho lookup O(1). Giả thiết: không chu trình, đúng 1 firstObject.