黑马程序员技术交流社区
标题: 【笔记】链表逆置 [打印本页]
作者: 倾心莫若初见 时间: 2016-10-21 11:23
标题: 【笔记】链表逆置
链表逆置算法是在面试中经常会遇到的试题，下面我们来分析一二。
首先链表结构如下：
typedefstruct _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
{
intdata; //数据域
struct_tag_listnode *next; //指向下一结点
}ListNode;
//逆置链表函数
voidlist_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;
}
}
//打印链表内容函数
voidlist_print(ListNode *phead)
{
ListNode *pcur = phead;
while (pcur->next != NULL)
{
printf("%d->", pcur->next->data);
pcur = pcur->next;
}
printf("NULL\n");
}
int main()
{
ListNodehead, 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);
}
经运行结果如下：
可以看到，我们的函数实现了对链表的逆置。
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |
