|
链表逆置算法是在面试中经常会遇到的试题，下面我们来分析一二。 首先链表结构如下： 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); } 经运行结果如下： 可以看到，我们的函数实现了对链表的逆置。
| 
收藏
淘帖
踩
