双向链表插入排序中尾指针维护异常问题排查与修复

首先，咱们先捋清楚你遇到的问题：你原来的代码只在链表头节点的next为空时更新尾指针，但这种情况只有链表刚初始化、仅含一个节点的时候才会触发。而当你插入更大的节点到链表尾部时（比如9、8、7这些数），头节点的next显然不是空的，所以尾指针根本没更新，还是停留在原来的尾节点上，反向打印的时候自然就遍历不到后面新增的节点了。

问题根源拆解 #

你写的if ((*top)->next == NULL) { *last = *top; }只覆盖了空链表插入第一个节点的场景，但插入排序中，更多的情况是往已有多个节点的链表尾部插入新节点，这时候这个判断完全不会触发，尾指针就一直指向旧的尾节点，导致后续遍历丢失新插入的尾部节点。

正确的尾指针维护思路 #

双向链表的插入排序中，尾指针需要在每次新节点成为链表最后一个节点时更新，同时还要处理好删除节点时的尾指针维护（毕竟你是先删节点再排序的）。下面给你具体的实现方案：

1. 先搞定删除节点时的尾指针维护

删除节点时，如果删的是尾节点，必须把尾指针更新为被删节点的前驱；如果删完链表空了，尾指针也要置空。示例代码（C语言）：

void deleteNode(Node** top, Node** last, int position) {
    if (*top == NULL) return; // 空链表直接返回

    Node* temp = *top;
    int i;
    // 定位到要删除的节点
    for (i = 0; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    if (temp == NULL) return; // 位置无效，直接返回

    // 情况1：删除头节点
    if (*top == temp) {
        *top = temp->next;
        if (*top != NULL) {
            (*top)->prev = NULL;
        } else {
            *last = NULL; // 删完链表空了，尾指针也置空
        }
    }
    // 情况2：删除尾节点
    else if (*last == temp) {
        *last = temp->prev;
        (*last)->next = NULL;
    }
    // 情况3：删除中间节点
    else {
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
    }

    free(temp);
}

2. 插入排序时的尾指针维护

在sortedInsert函数中，要判断新节点是否插入到了尾部，只有这种情况才更新尾指针。完整的sortedInsert实现：

void sortedInsert(Node** top, Node** last, Node* newNode) {
    Node* current;

    // 空链表：新节点既是头也是尾
    if (*top == NULL) {
        *top = newNode;
        *last = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
        return;
    }

    // 插在头部：尾指针不变（除非原来只有一个节点，但这里链表非空，所以尾还是原来的）
    if (newNode->data <= (*top)->data) {
        newNode->next = *top;
        (*top)->prev = newNode;
        *top = newNode;
        newNode->prev = NULL;
        return;
    }

    // 找到插入位置：第一个比新节点大的节点的前驱
    current = *top;
    while (current->next != NULL && current->next->data < newNode->data) {
        current = current->next;
    }

    // 情况1：插在尾部（current是原来的尾节点）
    if (current->next == NULL) {
        current->next = newNode;
        newNode->prev = current;
        newNode->next = NULL;
        *last = newNode; // 这里必须更新尾指针！
    }
    // 情况2：插在中间
    else {
        newNode->next = current->next;
        current->next->prev = newNode;
        current->next = newNode;
        newNode->prev = current;
        // 尾指针不变，因为链表尾部没变化
    }
}

关键注意点 #

• 插入时：只有当新节点被挂在原来尾节点的next上时，才更新*last为新节点，这是唯一需要更新尾指针的插入场景。
• 删除时：如果删除的是当前的*last节点，一定要把*last指向被删节点的prev，否则尾指针就失效了。
• 双向链表的每个操作都要保证prev和next指针的双向关联，任何一边断了都会导致链表遍历异常。

按照这个逻辑修改后，你再测试输入6 5 3 1 9 8 4 2 7 4 2并删除位置2的节点，反向打印就能完整输出所有节点了。

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