传智播客旗下技术交流社区北京校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 倾心莫若初见 中级黑马   /  2016-10-21 11:23  /  550 人查看  /  0 人回复  /   0 人收藏 保留作者信息 禁止商业使用(站长自定义文字)

链表逆置算法是在面试中经常会遇到的试题,下面我们来分析一二。
首先链表结构如下:
typedefstruct _tag_listnode
{
   int data; //数据域
   struct _tag_listnode *next; //下一个结点位置
}ListNode;
假设我们现在有如下链表:
11111.png
我们要对这个链表完成逆置。
思路:
(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);
}
经运行结果如下:
122222.png
可以看到,我们的函数实现了对链表的逆置。



分享至 : QQ空间
收藏

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马
关闭

站长推荐 上一条 /4 下一条