不交换节点的单链表选择排序实现问题咨询

你的代码存在以下几处核心逻辑错误，会导致运行结果异常甚至崩溃：

• AddLastNODE函数语法逻辑错误：else分支缺少花括号，导致mylist.pTail = p;语句无论链表是否为空都会执行，空链表插入时逻辑直接出错。
• 未从原链表移除已选出的最小节点：每次找到min节点后仅添加到临时链表，没有将其从原链表中摘除，后续遍历会重复选中同一个节点，且原链表节点的next指针未处理会导致新链表出现环、多余节点等异常。
• for循环判断顺序错误：遍历原链表的循环条件p->pNext!=NULL && p!=NULL顺序写反，若p为NULL时会先访问p->pNext触发空指针访问崩溃。
• 遗漏原链表最后一个节点：循环终止条件会跳过原链表的最后一个节点，导致排序后的链表缺失末尾元素。
• 新链表尾节点未置空：临时链表拼接完成后没有给尾节点的pNext赋值为NULL，链表遍历会出现越界。
• 初始化函数笔误：原代码中IntList(mylisttemp)大概率是InitList初始化函数的拼写错误。

修正后可运行代码 #

// 尾插节点函数修正
void AddLastNODE(LIST &mylist, NODE *p)
{
    // 插入前先将节点的next置空，避免残留原链表指针
    p->pNext = NULL;
    // 检查链表是否为空
    if(isEmpty(mylist))
        mylist.pHead = mylist.pTail = p;
    else
    { // 补充花括号保证逻辑正确
        mylist.pTail->pNext = p;
        mylist.pTail = p;
    }
}

// 工具函数：从链表中删除指定节点并更新链表指针
NODE* RemoveNode(LIST &mylist, NODE *target)
{
    NODE *cur = mylist.pHead;
    NODE *pre = NULL;
    while(cur != NULL && cur != target)
    {
        pre = cur;
        cur = cur->pNext;
    }
    if(cur == NULL) return mylist.pHead;
    // 处理头节点删除场景
    if(pre == NULL)
        mylist.pHead = cur->pNext;
    else
        pre->pNext = cur->pNext;
    // 处理尾节点删除场景
    if(cur == mylist.pTail)
        mylist.pTail = pre;
    return mylist.pHead;
}

void selectionSort(LIST &mylist)
{
    // 初始化临时链表存储有序节点
    LIST mylisttemp;
    InitList(mylisttemp);
    NODE *i;
    NODE *min;
    // 空链表或只有一个节点直接返回
    if(mylist.pHead == NULL || mylist.pHead == mylist.pTail)
        return;
    // 遍历直到原链表所有节点都被转移到临时链表
    while(mylist.pHead != NULL)
    {
        min = mylist.pHead;
        // 遍历找到当前原链表的最小节点
        for(i = mylist.pHead->pNext; i != NULL; i = i->pNext)
        {
            if(i->data < min->data)
                min = i;
        }
        // 把最小节点从原链表移除
        RemoveNode(mylist, min);
        // 添加到临时链表尾部
        AddLastNODE(mylisttemp, min);
    }
    // 将排序后的临时链表赋值给原链表
    mylist = mylisttemp;
}

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