C语言实现单链表逆序与逆序输出实例

1. 目标：单链表逆序输出（不修改结构）

当只需要打印结果而保持原链表不变时，可以利用系统调用栈或显式栈来模拟逆序访问。这里介绍两种常用思路：

第1步：使用递归天然栈特性

• 目的：利用函数调用的压栈过程到达链表尾部，在回溯阶段打印数据。
• 关键逻辑：先递归移动到 p->next，若为空则返回；否则在递归返回后执行 cout << p->data。
• 特点：无需额外分配内存，但链表过长可能导致栈溢出。

第2步：使用 std::stack 容器

• 目的：通过显式的数据结构存储节点值，手动控制后进先出顺序。
• 操作：遍历链表将所有 data 压入 stack<int>，随后循环 pop() 并打印。
• 适用场景：需要频繁多次逆序查看且不希望递归消耗过多栈帧时。

#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;

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

// 尾部插入新节点
node * add(int n, node * head){
 node * t = new node;
 t->data = n;
 t->next = NULL;
 if (head == NULL){
  head = t;
 }
 else if (head->next == NULL){
  head->next = t;
 }
 else{
  node * p = head->next;
  while (p->next != NULL){
   p = p->next;
  }
  p->next = t;
 }
 return head;
}

// 常规正序输出
void print(node * head){
 node * p = head;
 while (p != NULL){
  cout << p->data << " ";
  p = p->next;
 }
 cout << endl;
}

// 方法A：递归逆序输出
void reversePrint(node * p){
 if (p != NULL){
  reversePrint(p->next);
  cout << p->data << " ";
 }
}

// 方法B：栈逆序输出
void reversePrint2(node * head){
 stack<int> s;
 // 遍历并压栈
 while (head != NULL){
  s.push(head->data);
  head = head->next;
 }
 // 弹栈并打印
 while (!s.empty()){
  cout << s.top() << " ";
  s.pop();
 }
}

int main(){
 // 构建链表: 1 -> 2 -> 3 -> 4 -> 5
 node * head = NULL;
 for (int i = 1; i <= 5; i++){
  head = add(i, head);
 }

 cout << "Original: ";
 print(head);     

 cout << "Recursive Reverse: ";
 reversePrint(head); 
 cout << endl;

 cout << "Stack Reverse: ";
 reversePrint2(head); 
 cout << endl;

 system("pause");
 return 0;
}

2. 目标：真正的单链表逆序（修改指向）

此操作会改变节点的 next 指针方向，使原尾节点变为新头节点。核心难点在于处理指针指向的断开与重连。以下是两种主流解法：

第1步：循环法（迭代）- 三指针移动

• 参数说明：
  - p1: 前驱节点 (Predecessor)
  - p2: 当前节点 (Current)
  - p3: 后继节点 (Successor)
• 操作流程：
  1. 初始状态：p1=head, p2=head->next, p1->next=NULL。
  2. 循环直到 p2 为 NULL:
  a. 暂存后继：p3 = p2
  b. 更新当前指针：p2 = p2->next
  c. **逆转指向**：p3->next = p1（关键步骤）
  d. 前移两个指针：p1 = p3
  3. 最终将 head 指向 p1。
• 优势：空间复杂度 O(1)，时间复杂度 O(N)，不易受系统栈限制影响。

// 循环逆序实现
node * reverse(node * head) {
 if (head == NULL || head->next == NULL) {
  return head;
 }

 node * p1 = head;
 node * p2 = head->next;
 node * p3 = NULL; 
 head->next = NULL; // 原头节点变尾节点

 while (p2 != NULL){
  p3 = p2;
  p2 = p2->next;
  p3->next = p1; // 逆转指针
  p1 = p3;
 }
 head = p1; // 更新头节点
 return head;
}

第2步：递归法 - 自底向上重置指针

• 逻辑核心：假设从第二个节点开始的链表已经逆序完成，该子链表的新的尾部就是原链表的第二个节点（即 p->next），我们将它的 next 指向自己，然后把自己置空成为新尾部。
• 操作细节： 1. 递归终止条件：p==NULL 或 p->next==NULL。 2. 获取子链表的头部： node * newHead = reverse2(p->next)。 3. 反转指向：p->next->next = p。
• 注意：p->next = NULL 必须执行，否则原头节点会产生环。

// 递归逆序实现
node * reverse2(node * p) {
 if (p == NULL || p->next == NULL) {
  return p;
 }

 // 递归处理后续节点，newHead是逆序后的头节点
 node * newHead = reverse2(p->next);
 
 // 关键指针翻转
 p->next->next = p; // 下一个节点指回自己
 p->next = NULL;     // 切断原方向的连接
 
 return newHead;
}

综合测试主函数

以下代码演示了如何调用上述逆序函数及验证结果：

int main(){
 node * head = NULL;
 // 构建链表
 for (int i = 1; i <= 5; i++){
  head = add(i, head);
 }

 print(head); // 输出: 1 2 3 4 5
 
 // 循环逆序
 head = reverse(head);
 print(head); // 输出: 5 4 3 2 1
 
 // 递归逆序（需重新构建或使用另一副本，此处仅示意功能）
 // head = reverse2(head); 
 // print(head); 

 system("pause");
 return 0;
}

总结

单链表的逆序操作是理解指针移动的绝佳案例。对于简单的显示需求，递归打印最为简洁；对于结构性的反转，推荐使用循环的三指针法，它直观且高效。递归反转法则更具算法美感，但在调试时需要理清“回溯”阶段的指针重定向逻辑。以上就是C语言实现单链表逆序与逆序输出的详细内容，更多关于C语言链表操作、数据结构算法学习的资料请关注本站其它相关文章！