当前位置：首页 > JavaScript

js实现无序链表排序

2026-04-04 17:47:28JavaScript

无序链表排序方法

在JavaScript中，实现无序链表的排序通常可以采用多种方法。以下是几种常见的排序方法及其实现方式。

链表节点定义

在开始排序之前，需要定义链表节点的结构。链表节点通常包含一个值和一个指向下一个节点的指针。

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

插入排序

插入排序是一种简单直观的排序方法，适用于链表结构。它的基本思想是将未排序部分的节点逐个插入到已排序部分的合适位置。

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

  let dummy = new ListNode(0);
  dummy.next = head;
  let lastSorted = head;
  let curr = head.next;

  while (curr) {
    if (lastSorted.val <= curr.val) {
      lastSorted = lastSorted.next;
    } else {
      let prev = dummy;
      while (prev.next.val <= curr.val) {
        prev = prev.next;
      }
      lastSorted.next = curr.next;
      curr.next = prev.next;
      prev.next = curr;
    }
    curr = lastSorted.next;
  }
  return dummy.next;
}

归并排序

归并排序是一种高效且稳定的排序算法，特别适合链表结构。它的基本思想是将链表分成两半，递归排序每一半，然后合并两个有序链表。

function mergeSortList(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;
  }
  let mid = slow.next;
  slow.next = null;

  let left = mergeSortList(head);
  let right = mergeSortList(mid);

  return merge(left, right);
}

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

  while (l1 && l2) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

快速排序

快速排序也可以用于链表排序，但实现起来较为复杂。它的基本思想是选择一个基准节点，将链表分为小于基准和大于基准的两部分，然后递归排序这两部分。

js实现无序链表排序

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

  let pivot = head;
  let smaller = new ListNode(0);
  let greater = new ListNode(0);
  let smallerTail = smaller;
  let greaterTail = greater;
  let curr = head.next;

  while (curr) {
    if (curr.val < pivot.val) {
      smallerTail.next = curr;
      smallerTail = smallerTail.next;
    } else {
      greaterTail.next = curr;
      greaterTail = greaterTail.next;
    }
    curr = curr.next;
  }
  smallerTail.next = null;
  greaterTail.next = null;

  let sortedSmaller = quickSortList(smaller.next);
  let sortedGreater = quickSortList(greater.next);

  pivot.next = sortedGreater;
  if (!sortedSmaller) return pivot;

  let tail = sortedSmaller;
  while (tail.next) {
    tail = tail.next;
  }
  tail.next = pivot;
  return sortedSmaller;
}