如何在JavaScript中将链表按字母顺序排序后打印输出

你可以通过插入排序实现需求，该方案适配链表的结构特性，实现逻辑简单，符合课后作业的实现要求。

核心实现代码 #

你只需要在LinkedList类中新增如下排序方法即可：

sortAlphabetically() {
  // 空链表或仅有一个节点时无需排序
  if (!this.head || !this.head.next) return;

  // 哨兵节点简化头节点插入逻辑
  const sortedDummyHead = new Node(null);
  let currentUnsorted = this.head;

  while (currentUnsorted) {
    // 暂存下一个未排序节点，避免插入操作断链
    const nextUnsorted = currentUnsorted.next;

    // 找到已排序链表中适合插入的位置
    let insertPrev = sortedDummyHead;
    // localeCompare方法按字母顺序对比字符串，返回小于0说明前值更小
    while (insertPrev.next && insertPrev.next.data.localeCompare(currentUnsorted.data) < 0) {
      insertPrev = insertPrev.next;
    }

    // 完成节点插入
    currentUnsorted.next = insertPrev.next;
    insertPrev.next = currentUnsorted;

    // 处理下一个未排序节点
    currentUnsorted = nextUnsorted;
  }

  // 更新原链表头为排序后链表的头
  this.head = sortedDummyHead.next;
}

调用方式 #

在打印链表前调用该方法即可：

// 新增排序调用
l.sortAlphabetically();
console.log(l.printList());

完整可运行代码 #

console.log("*********** Section: 2 ***********");
console.log("Sorted Book List");

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  printList() {
    if (!this.head) {
      return;
    }
    let node = this.head;
    let str = "";
    while (node) {
      str += node.data + " ";
      node = node.next;
    }
    return str;
  }
  sortAlphabetically() {
    // 空链表或仅有一个节点时无需排序
    if (!this.head || !this.head.next) return;

    // 哨兵节点简化头节点插入逻辑
    const sortedDummyHead = new Node(null);
    let currentUnsorted = this.head;

    while (currentUnsorted) {
      // 暂存下一个未排序节点，避免插入操作断链
      const nextUnsorted = currentUnsorted.next;

      // 找到已排序链表中适合插入的位置
      let insertPrev = sortedDummyHead;
      // localeCompare方法按字母顺序对比字符串，返回小于0说明前值更小
      while (insertPrev.next && insertPrev.next.data.localeCompare(currentUnsorted.data) < 0) {
        insertPrev = insertPrev.next;
      }

      // 完成节点插入
      currentUnsorted.next = insertPrev.next;
      insertPrev.next = currentUnsorted;

      // 处理下一个未排序节点
      currentUnsorted = nextUnsorted;
    }

    // 更新原链表头为排序后链表的头
    this.head = sortedDummyHead.next;
  }
}

const a = new Node("To Kill a Mockingbird, ");
const b = new Node("Huckleberry Finn, ");
const c = new Node("Pride and Prejudice, ");
const d = new Node("Lord of the Flies, ");
const e = new Node("Alice in Wonderland, ");
const f = new Node("The Old Man and the Sea, ");
const g = new Node("Atlas Shrugged");

l = new LinkedList();
l.head = a;
a.next = b;
b.next = c;
c.next = d;
d.next = e;
e.next = f;
f.next = g;

// 调用排序方法
l.sortAlphabetically();
console.log(l.printList());

运行后输出的排序结果为：
Alice in Wonderland, Atlas Shrugged Huckleberry Finn, Lord of the Flies, Pride and Prejudice, The Old Man and the Sea, To Kill a Mockingbird,

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