C++培训之必备面试题之链表逆置

链表逆置算法是在面试中经常会遇到的试题，下面我们来分析一二。
首先链表结构如下：
typedef struct _tag_listnode
{
int data; //数据域
struct _tag_listnode *next; //下一个结点位置
}ListNode;
假设我们现在有如下链表：
 
我们要对这个链表完成逆置。
思路：

1. 用一个ListNode*指针pcur指向head->next,然后让head->next指向NULL,此时我们把head看成是一个带头的空链表;
2. 将pcur所在链表的每一个结点，用头插法插入到head所在的链表中，这样我们就完成的链表的逆置.

参考代码如下：
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _tag_listnode
{
int data; //数据域
struct _tag_listnode *next; //指向下一结点
}ListNode;
 
//逆置链表函数
void list_reverse(ListNode *phead)
{
ListNode *pcur = phead->next; //将pcur指向链表头结点的下一结点
phead->next = NULL; //建立一个头为phead的空链表
 
//循环将pcur所在链表的每一个结点用头插法插入到空链表中
while (pcur != NULL)
{
ListNode *tmp = pcur->next; //tmp指向pcur的下一个结点
//将pcur指向的结点用头插法插入链表
pcur->next = phead->next;
phead->next = pcur;
 
pcur = tmp;
}
}
 
//打印链表内容函数
void list_print(ListNode *phead)
{
ListNode *pcur = phead;
 
while (pcur->next != NULL)
{
printf("%d->", pcur->next->data);
pcur = pcur->next;
}
printf("NULL\n");
}
 
int main()
{
ListNode head, node1, node2, node3, node4, node5;
 
//创建一个链表如图
node1.data = 12; node1.next = &node2;
node2.data = 21; node2.next = &node3;
node3.data = 35; node3.next = &node4;
node4.data = 46; node4.next = NULL;
head.next = &node1;
 
//打印链表内容
list_print(&head);
 
//逆置链表
list_reverse(&head);
 
//打印链表内容
list_print(&head);
 
}
经运行结果如下：
 
可以看到，我们的函数实现了对链表的逆置。

 本文版权归传智播客C++培训学院所有，欢迎转载，转载请注明作者出处。谢谢！
作者：传智播客C/C++培训学院
首发：http://www.itcast.cn/c/