C语言双向链表插入排序问题求助：代码陷入无限循环

咱们先来拆解你遇到的问题——双向链表插入排序陷入无限循环，还一直输出8和9，核心问题出在你对插入排序的逻辑理解偏差，以及双向链表指针操作的错误上。

双向链表插入排序的正确设计思路 #

插入排序的核心是逐步构建有序链表，和数组插入排序逻辑类似，但因为是链表，要重点处理指针的双向维护：

• 首先，准备一个空的「已排序链表」表头（你代码里定义了headsorted但没用到，这正是关键）。
• 遍历原链表的每个节点，把当前节点从原链表中移除（注意断开它和前后节点的连接）。
• 在已排序链表中，从表头开始遍历，找到第一个数据大于当前节点的位置，把当前节点插入到这个位置的前面；如果所有节点都比当前节点小，就插在已排序链表的末尾。
• 插入时必须同时维护前后节点的previous和next指针：
  1. 让当前节点的next指向插入位置的节点
  2. 让当前节点的previous指向插入位置节点的前驱
  3. 更新插入位置前驱节点的next为当前节点
  4. 更新插入位置节点的previous为当前节点（如果不是插在末尾的话）

你代码里的关键错误 #

1. 逻辑完全搞错：你把插入排序写成了冒泡排序的交换逻辑，而且交换指针的方式直接导致循环引用——current->next = temp这一步让current和temp互相指向，直接造成链表循环，这就是无限输出的根源。
2. 内存泄漏：你先malloc了temp，然后直接赋值temp = head，导致刚分配的内存地址丢失，永远无法释放。
3. 空指针风险：while循环的条件顺序错误，应该先判断current != NULL和current->next != NULL，再判断current->data > current->next->data，不然会出现空指针访问崩溃。
4. 未利用已排序链表表头：你没有用headsorted来构建有序链表，而是在原链表上乱改指针，导致链表结构彻底混乱。

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* previous;
} Node;

Node* head = NULL;
Node* headsorted = NULL; // 已排序链表的表头

// 向原链表头部插入节点（你的插入逻辑没问题，保留）
void Insert(int x) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->next = head;
    temp->previous = NULL;
    if (head != NULL) {
        head->previous = temp;
    }
    head = temp;
}

// 打印链表
void Print(Node* listHead) {
    Node* temp = listHead;
    printf("List is: ");
    while(temp != NULL) {
        printf(" %d", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 双向链表的插入排序实现
void InsertSort() {
    printf("\nInsert Sort begins...\n");
    if (head == NULL || head->next == NULL) {
        printf("\nList Error or already sorted!\n");
        headsorted = head;
        return;
    }

    Node* current = head;
    while (current != NULL) {
        // 保存当前节点的下一个节点，防止断链
        Node* nextNode = current->next;

        // 把当前节点从原链表中移除
        if (current->previous != NULL) {
            current->previous->next = nextNode;
        } else {
            // 如果是原链表表头，更新原表头
            head = nextNode;
        }
        if (nextNode != NULL) {
            nextNode->previous = current->previous;
        }

        // 在已排序链表中找到插入位置
        Node* sortedPtr = headsorted;
        Node* insertPrev = NULL;
        while (sortedPtr != NULL && sortedPtr->data < current->data) {
            insertPrev = sortedPtr;
            sortedPtr = sortedPtr->next;
        }

        // 插入当前节点到已排序链表
        current->next = sortedPtr;
        current->previous = insertPrev;

        if (insertPrev == NULL) {
            // 插在已排序链表的头部
            headsorted = current;
        } else {
            insertPrev->next = current;
        }
        if (sortedPtr != NULL) {
            sortedPtr->previous = current;
        }

        // 处理下一个节点
        current = nextNode;
    }
}

int main() {
    head = NULL;
    FILE *file = fopen("List.txt", "r");
    if (file == NULL) {
        printf("Failed to open file!\n");
        return 1;
    }

    int l;
    int length = 0;
    // 修正文件读取逻辑，避免多读一次
    while (fscanf(file, "%d", &l) == 1) {
        Insert(l);
        length++;
    }
    fclose(file);

    printf("Original ");
    Print(head);

    InsertSort();

    printf("Sorted ");
    Print(headsorted);

    return 0;
}

代码说明 #

• 我们单独用headsorted来维护已排序的链表，原链表的节点会被逐个移到这里。
• 每次处理节点时，先把它从原链表中“摘出来”，再插入到已排序链表的正确位置。
• 所有指针操作都同时维护previous和next，确保双向链表的结构正确，不会出现循环或断链。
• 修正了文件读取的逻辑，避免feof导致的多读问题。

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