当前位置：首页 > JavaScript

js实现无序链表排序

2026-03-01 16:57:20JavaScript

无序链表排序的实现方法

在JavaScript中实现无序链表的排序，可以采用多种排序算法。以下介绍两种常见方法：归并排序和插入排序。

归并排序实现

归并排序适合链表的排序，时间复杂度为O(n log n)，空间复杂度为O(1)。

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function sortList(head) {
  if (!head || !head.next) return head;

  let slow = head;
  let fast = head.next;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  const mid = slow.next;
  slow.next = null;

  const left = sortList(head);
  const right = sortList(mid);

  return merge(left, right);
}

function merge(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  curr.next = l1 || l2;

  return dummy.next;
}

插入排序实现

插入排序实现简单，但时间复杂度为O(n²)，适合小规模数据。

function insertionSortList(head) {
  const dummy = new ListNode(0);
  let curr = head;

  while (curr) {
    const next = curr.next;
    let prev = dummy;

    while (prev.next && prev.next.val < curr.val) {
      prev = prev.next;
    }

    curr.next = prev.next;
    prev.next = curr;
    curr = next;
  }

  return dummy.next;
}

使用示例

// 创建链表: 4->2->1->3
const head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));

// 使用归并排序
const sortedHead = sortList(head);

// 使用插入排序
// const sortedHead = insertionSortList(head);

// 打印排序结果
let current = sortedHead;
while (current) {
  console.log(current.val);
  current = current.next;
}