C语言单链表冒泡排序后链表长度缩短bug排查

• 问题1：swap函数修改头指针逻辑无效
  C语言为值传递机制，swap函数形参Node* first是实参的拷贝，函数内部对first的赋值仅作用于函数内部，不会修改外部的头指针。当需要交换头结点和后继节点时，头指针未正确更新，会直接导致链表头部丢失、节点断裂。
• 问题2：bubbleSort中交换节点后未更新prev和cur的指向
  调用swap交换cur和cur->next的位置后，二者的先后顺序已经反转，但原有代码仍沿用交换前的指向执行prev = cur; cur = next，会直接跳过已经换到前面的节点，最终导致节点漏遍历、链表长度缩短。
• 问题3：基础函数存在语法缺陷
  initNode函数声明为返回Node*类型，但代码中缺少return newN语句，返回随机内存地址，会导致节点创建异常；printNodes函数判断条件为cur->next != NULL，会漏掉最后一个节点的打印。

1. 修复swap函数，改为二级指针传递头指针 #

void swap(Node* prev, Node* cur, Node** first){
  Node* next = cur->next;
  if(next==NULL){return;}
  Node* nextO = next->next;
  cur->next = nextO;
  if(prev != NULL){
    prev->next = next;
  }else{
    *first = next; // 解引用二级指针直接修改外部头指针
  }
  next->next = cur;
}

2. 修复bubbleSort函数，调整交换后的指针移动逻辑 #

void bubbleSort(Node** first){ // 接收二级头指针
  int switchC = -1;
  while(switchC != 0){
    switchC = 0;
    Node* cur = *first;
    Node* prev = NULL;
    Node* next = NULL;
    while(cur->next != NULL){
      next = cur->next;
      if(next->data <= cur->data){
        swap(prev, cur, first);
        switchC++;
        // 交换后next已移动到cur前方，更新prev为next，cur保持不变继续比较后续节点
        prev = next;
      }else{
        // 未交换时按原逻辑移动指针
        prev = cur;
        cur = next;
      }
    }
  }
}

3. 修复基础函数的语法缺陷 #

// 修复initNode的返回值
Node* initNode(){
  Node* newN = malloc(sizeof(Node));
  newN->data = rand() % 1000;
  newN->next = NULL;
  return newN; // 补充节点返回逻辑
}

// 修复printNodes的打印范围
void printNodes(Node* first){
  Node* cur = first;
  while(cur != NULL){ // 修改遍历条件，覆盖所有节点
    printf("%d-", cur->data);
    cur = cur->next;
  }
}

4. 修改main函数的调用逻辑 #

int main(){ // 符合C标准的main函数返回值定义
  Node* first = initNode();
  addNodes(10, first);
  printf("排序前：");
  printNodes(first);
  bubbleSort(&first); // 传入头指针的地址
  printf("\n排序后：");
  printNodes(first);
  return 0;
}

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