如何在JavaScript中对图书链表按字母顺序排序

原有代码存在的问题 #

原sortList()方法主要有以下几处错误：

• 错误使用Set存储节点，Set原型没有sort排序方法，需要转为普通数组存储
• 遍历链表时错误读取current.link属性，Book类定义的后继节点属性为next
• 直接对节点实例排序，没有提取图书名称element属性作为排序依据
• 调用insertAt时参数传入错误，不需要重复创建Book实例，且该方法第一个参数接收的是图书名称值而非节点对象
• 倒序插入逻辑冗余，不需要反向遍历排序后的数组

修复后的完整代码 #

class Book {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Books {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(element) { //添加图书
    var node = new Book(element);
    var current;
    if (this.head == null) this.head = node;
    else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  insertAt(element, index) { //在指定索引位置插入图书
    if (index < 0 || index > this.size)
      return console.log("请输入合法索引。");
    else {
      var node = new Book(element);
      var curr, prev;

      curr = this.head;

      if (index == 0) {
        node.next = this.head;
        this.head = node;
      } else {
        curr = this.head;
        var it = 0;

        while (it < index) {
          it++;
          prev = curr;
          curr = curr.next;
        }

        node.next = curr;
        prev.next = node;
      }
      this.size++;
    }
  }

  sortList() { //按图书名称字母顺序排序，返回排序后的链表
    const bookNameArr = [];
    let current = this.head;
    // 遍历提取所有图书名称
    while (current != null) {
      bookNameArr.push(current.element);
      current = current.next;
    }
    // 按字母顺序排序，支持中/英文通用排序规则
    bookNameArr.sort((a, b) => a.localeCompare(b));
    // 构建排序后的新链表
    const sortedList = new Books();
    bookNameArr.forEach(name => sortedList.add(name));
    return sortedList;
  }

  // 辅助方法：直接打印所有图书名称，便于快速查看结果
  printAll() {
    let current = this.head;
    const res = [];
    while(current) {
      res.push(current.element);
      current = current.next;
    }
    console.log(res);
  }
}

var bookList = new Books();
// 打乱顺序添加测试用例
bookList.add("dbook4");
bookList.add("abook1");
bookList.add("hbook8");
bookList.add("bbook2");
bookList.add("ebook5");
bookList.add("gbook7");
bookList.add("cbook3");
bookList.add("fbook6");

const sortedBooks = bookList.sortList();
sortedBooks.printAll(); // 输出 ['abook1','bbook2','cbook3','dbook4','ebook5','fbook6','gbook7','hbook8']
console.log(sortedBooks); // 打印完整排序后的链表结构

实现说明 #

• 使用localeCompare进行字符串排序，相比直接比较大小的写法更稳定，同时支持中文图书名按拼音排序的需求
• 先提取所有书名排序后再批量构建新链表，时间复杂度由排序逻辑决定为O(nlogn)，相比链表原地排序的写法可读性更高，更适合业务场景使用

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