双向链表插入排序的原理与O(1)空间实现辨析

public static List sort(List list) {        
    List sortedList = new List();                  // 1. 创建一个新的空列表
    List.Iter curIndex = List.Iter.last(sortedList);  // 终止前向迭代器        

    for(List.Iter iter = List.Iter.first(list); !iter.end(); iter.next()) {
        curIndex = List.Iter.last(sortedList);
        List.Node node = iter.key_data();  // 2. 获取原列表节点的数据

        // ... 省略寻找插入位置的逻辑 ...

        // 3. 将节点数据插入到 sortedList 中
        sortedList.insAfter(curIndex, node.key, node.data);                
    }
    return sortedList; // 返回新创建的排序列表
}

// 假设双向链表节点结构
class Node {
    int key;
    Object data;
    Node prev;
    Node next;

    public Node(int key, Object data) {
        this.key = key;
        this.data = data;
        this.prev = null;
        this.next = null;
    }

    // 方便打印
    @Override
    public String toString() {
        return "{" + key + ":" + data + "}";
    }
}

// 假设一个简单的双向链表类，包含head和tail
class List {
    Node head;
    Node tail;

    public List() {
        this.head = null;
        this.tail = null;
    }

    public void add(int key, Object data) {
        Node newNode = new Node(key, data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    /**
     * 真正的链表插入排序，通过重连节点实现O(1)额外空间
     * @param originalList 原始链表
     * @return 排序后的链表（头节点）
     */
    public static List insertionSort(List originalList) {
        if (originalList == null || originalList.head == null || originalList.head.next == null) {
            return originalList; // 0或1个节点的列表已排序
        }

        List sortedList = new List(); // 用于构建排序后的链表，但重用节点

        Node currentUnsorted = originalList.head;
        while (currentUnsorted != null) {
            Node nextUnsorted = currentUnsorted.next; // 记录下一个待处理的节点

            // 1. 将当前节点从原链表中逻辑上“解链”（为了简化，这里直接处理currentUnsorted）
            // 关键是确保currentUnsorted的prev和next在插入到sortedList时被正确设置
            currentUnsorted.prev = null; // 清除旧的连接
            currentUnsorted.next = null;

            // 2. 找到当前节点在 sortedList 中的正确插入位置
            if (sortedList.head == null || currentUnsorted.key < sortedList.head.key) {
                // 插入到已排序列表的头部
                currentUnsorted.next = sortedList.head;
                if (sortedList.head != null) {
                    sortedList.head.prev = currentUnsorted;
                }
                sortedList.head = currentUnsorted;
                if (sortedList.tail == null) { // 如果是第一个节点
                    sortedList.tail = currentUnsorted;
                }
            } else {
                Node search = sortedList.head;
                // 找到第一个 key 大于或等于 currentUnsorted.key 的节点
                // 或者遍历到链表尾部
                while (search.next != null && search.next.key < currentUnsorted.key) {
                    search = search.next;
                }
                // 插入到 search 之后
                currentUnsorted.next = search.next;
                if (search.next != null) {
                    search.next.prev = currentUnsorted;
                }
                currentUnsorted.prev = search;
                search.next = currentUnsorted;

                if (currentUnsorted.next == null) { // 如果插入到了尾部
                    sortedList.tail = currentUnsorted;
                }
            }
            currentUnsorted = nextUnsorted; // 处理下一个未排序节点
        }
        return sortedList;
    }

    public static void main(String[] args) {
        List myList = new List();
        myList.add(5, "apple");
        myList.add(2, "banana");
        myList.add(8, "cherry");
        myList.add(1, "date");
        myList.add(6, "elderberry");

        System.out.println("原始列表:");
        myList.printList();

        List sortedMyList = List.insertionSort(myList);
        System.out.println("排序后列表:");
        sortedMyList.printList();
    }
}