双向链表按年份+字母排序异常：插入排序实现求助

原代码存在的问题 #

1. 节点丢失：

   • 手动逐个字符比较片名时，未处理字符串长度不一致的情况，会触发StringIndexOutOfBoundsException，导致节点无法插入。
   • 当新节点片名大于头节点片名时，无对应处理逻辑，循环会无限执行直至抛出异常，节点直接丢失。

2. 排序逻辑失效：

   • 年份相等时仅与头节点比较，未遍历整个同年份节点链表，无法找到正确插入位置。
   • 遍历分支仅判断年份小于的情况，未处理年份相等但片名需排序的场景，导致同年份节点无法按片名排序。

修复方案 #

1. 统一比较逻辑

提取辅助方法，统一处理电影年份和片名的比较，避免手动字符比较的错误：

// 比较两个电影：先按年份升序，年份相同则按片名字典序升序
private static int compareMovies(Movie m1, Movie m2) {
    // 优先比较年份
    if (m1.releaseDate != m2.releaseDate) {
        return Integer.compare(m1.releaseDate, m2.releaseDate);
    }
    // 年份相同，用String自带的字典序比较
    return m1.movieName.compareTo(m2.movieName);
}

2. 重写sortedInsert方法

基于辅助方法，重新实现插入逻辑，覆盖所有场景：

public static Node sortedInsert(Node headRef, Node newNode) {
    Node current;

    // 空链表直接返回新节点
    if (headRef == null) {
        headRef = newNode;
    } 
    // 新节点比头节点小，插入到头部
    else if (compareMovies(newNode.movie, headRef.movie) < 0) {
        newNode.next = headRef;
        headRef.prev = newNode;
        headRef = newNode;
    } 
    // 遍历链表找到正确插入位置
    else {
        current = headRef;
        // 找到第一个比新节点大的节点，插入到它前面
        while (current.next != null && compareMovies(current.next.movie, newNode.movie) <= 0) {
            current = current.next;
        }
        // 处理双向链表的指针关联
        newNode.next = current.next;
        if (current.next != null) {
            current.next.prev = newNode;
        }
        current.next = newNode;
        newNode.prev = current;
    }

    return headRef;
}

3. insertionSort方法保持不变

原方法的逻辑（逐个取出原节点插入到已排序链表）是正确的，无需修改：

public static Node insertionSort(Node headRef) {
    Node sorted = null;
    Node current = headRef;
    
    while (current != null) {
        Node next = current.next;
        // 断开当前节点与原链表的关联
        current.prev = current.next = null;
        // 插入到已排序链表
        sorted = sortedInsert(sorted, current);
        current = next;
    }
    
    return sorted;
}

修复后效果 #

测试原输入链表：

1997 Titanic
1997 Fast & Furious
1999 The Matrix
2014 The Hobbit: The Battle of the Five Armies
2014 Interstellar

排序后会得到正确结果：

1997 Fast & Furious
1997 Titanic
1999 The Matrix
2014 Interstellar
2014 The Hobbit: The Battle of the Five Armies

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