单链表选择排序（交换节点迭代法）功能异常排查求助

你的选择排序实现存在几个关键问题，导致sort()函数无法正常工作：

1. 错误的排序逻辑：频繁交换而非找最小值后单次交换
   当前代码会在每遇到一个比当前节点小的节点就立即交换，这会导致链表结构频繁变化，后续的y = y->next会指向错误的节点（因为节点位置已经被交换），最终遍历混乱，排序失败。

2. 交换后指针未正确更新
   交换节点后，用来遍历的全局指针x并没有指向交换后的当前位置节点，仍然指向原来的节点，导致下一轮遍历的起始位置错误。

3. 全局变量滥用导致状态混乱
   全局的x、y、prev等指针在多个函数间共享，交换节点后这些指针的状态没有同步更新，进一步加剧了指针指向的混乱。

修复后的完整代码 #

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

typedef struct node {
    int data;
    struct node *next;
} node;

node *head = NULL;
static int k = 0; // 记录节点总数

// 创建新节点
node *make_node() {
    k++;
    return (node *)malloc(sizeof(node));
}

// 添加节点到链表尾部
void push() {
    node *new_node = make_node();
    printf("Enter Data: ");
    scanf("%d", &new_node->data);
    new_node->next = NULL;

    if (head == NULL) {
        head = new_node;
    } else {
        node *temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
}

// 根据位置获取节点及其前驱节点
void get_node_by_pos(int pos, node **prev_node, node **curr_node) {
    *prev_node = NULL;
    *curr_node = head;
    for (int l = 1; l < pos; l++) {
        *prev_node = *curr_node;
        *curr_node = (*curr_node)->next;
    }
}

// 交换两个位置的节点
void swap_node(int i, int j) {
    if (i == j) return; // 无需交换

    node *prevX, *currX;
    node *prevY, *currY;
    get_node_by_pos(i, &prevX, &currX);
    get_node_by_pos(j, &prevY, &currY);

    // 处理头节点交换情况
    if (prevX == NULL) {
        head = currY;
    } else {
        prevX->next = currY;
    }

    if (prevY == NULL) {
        head = currX;
    } else {
        prevY->next = currX;
    }

    // 交换next指针
    node *temp = currX->next;
    currX->next = currY->next;
    currY->next = temp;
}

// 选择排序：每轮找到最小节点，与当前节点交换
void sort() {
    for (int i = 1; i < k; i++) {
        // 找到从i到k中最小的节点位置
        int min_pos = i;
        node *curr_min;
        get_node_by_pos(i, NULL, &curr_min);

        node *curr_curr = curr_min->next;
        for (int j = i + 1; j <= k; j++) {
            if (curr_curr->data < curr_min->data) {
                curr_min = curr_curr;
                min_pos = j;
            }
            curr_curr = curr_curr->next;
        }

        // 如果最小节点不是当前节点，执行交换
        if (min_pos != i) {
            swap_node(i, min_pos);
        }
    }
}

// 打印链表
void print_node() {
    printf("------------Printing Node--------------\n");
    node *temp = head;
    while (temp != NULL) {
        printf("%d\n", temp->data);
        temp = temp->next;
    }
}

int main(void) {
    int choice;
    printf("MENU\n1-PUSH\n2-Sort and Print node\n");
    do {
        printf("Enter Your Choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                push();
                break;
            case 2:
                sort();
                print_node();
                break;
            default:
                printf("Wrong Choice!\n");
        }
    } while (choice == 1);

    // 释放内存，避免内存泄漏
    node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
    k = 0;
    return 0;
}

关键修改说明 #

1. 重构push函数：移除全局的prev和next指针，改用局部指针遍历到链表尾部添加节点，避免全局指针状态混乱。
2. 新增get_node_by_pos函数：专门用于根据位置获取节点及其前驱，简化交换逻辑，提升代码可读性。
3. 修复swap_node函数：统一处理所有交换场景（包括头节点），确保交换后链表指针完全正确。
4. 重写sort函数：实现标准选择排序逻辑，每轮仅找到最小节点后交换一次，避免频繁交换导致的遍历错误。
5. 添加内存释放：程序结束时释放链表内存，养成良好的内存管理习惯。

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