如何按next_id排序双向链表？需原生JS及Ramda.js实现思路

原生JavaScript实现 #

这里有个高效且贴合链表逻辑的原生JS实现方案，完全能满足你的需求：

const dll = [ 
  {id: '22', prev_id: '41', next_id: '45'}, 
  {id: '45', prev_id: '22', next_id: null}, 
  {id: '41', prev_id: '14', next_id: '22'}, 
  {id: '14', prev_id: null, next_id: '41'}, 
];

// 1. 构建id到节点的映射表，实现O(1)快速查找
const nodeMap = new Map();
dll.forEach(node => nodeMap.set(node.id, node));

// 2. 定位链表头节点（prev_id为null的节点）
const headNode = dll.find(node => node.prev_id === null);

// 3. 从头节点出发，按next_id顺序遍历收集节点
const sortedDll = [];
let current = headNode;
while (current) {
  sortedDll.push(current);
  // 根据next_id获取下一个节点，无next_id则终止遍历
  current = current.next_id ? nodeMap.get(current.next_id) : null;
}

console.log(sortedDll);
// 输出结果与你期望的排序数组完全一致

逻辑说明：

• 映射表构建：用Map存储节点id和对应节点，避免每次查找下一个节点时遍历整个数组，把查找时间从O(n)降到O(1)，节点数量多的时候优势明显。
• 头节点定位：双向链表的头节点特征就是prev_id为null，用find方法可以快速定位。
• 顺序遍历收集：沿着next_id的指向依次把节点加入结果数组，直到遇到尾节点（next_id为null）为止，完全贴合链表本身的结构，不会出现排序逻辑错误。

这种方法的时间复杂度是O(n)，比直接用数组sort方法（O(n log n)）更高效。

Ramda.js转换思路 #

如果要转成Ramda风格，可以利用Ramda的函数式工具简化代码：

1. 用R.indexBy(R.prop('id'))替代原生Map构建映射表；
2. 用R.find(R.propEq('prev_id', null))查找头节点；
3. 用R.unfold实现遍历收集逻辑（unfold适合从初始值生成序列，直到触发终止条件）。

示例代码如下：

const R = require('ramda');

const dll = [ 
  {id: '22', prev_id: '41', next_id: '45'}, 
  {id: '45', prev_id: '22', next_id: null}, 
  {id: '41', prev_id: '14', next_id: '22'}, 
  {id: '14', prev_id: null, next_id: '41'}, 
];

// 构建id到节点的映射
const nodeMap = R.indexBy(R.prop('id'), dll);
// 找到头节点
const headNode = R.find(R.propEq('prev_id', null), dll);
// 用unfold生成排序后的数组
const sortedDll = R.unfold(
  current => {
    if (!current) return false; // 终止条件：无当前节点则停止迭代
    // 返回当前节点和下一个迭代的节点（如果存在）
    const nextNode = R.prop('next_id', current) ? R.prop(R.prop('next_id', current), nodeMap) : null;
    return [current, nextNode];
  },
  headNode
);

console.log(sortedDll);

R.unfold的逻辑和原生while循环一致：每次返回当前元素和下一个迭代的初始值，直到返回false时停止，最终生成完整的排序序列。

内容的提问来源于stack exchange，提问作者Arthur