Chinaunix首页 | 论坛 | 博客
  • 博客访问: 208085
  • 博文数量: 131
  • 博客积分: 259
  • 博客等级: 二等列兵
  • 技术积分: 705
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-21 21:15
文章分类

全部博文(131)

文章存档

2013年(3)

2011年(128)

分类:

2011-10-09 10:13:15

原文地址:链表就地逆置 作者:曹朋Code

笔者对于这个链表的就地逆置算法感觉比较绕!今天就彻底的消灭了他。现将总结如下。
就地逆置,就是在不借助任何中间变量的情况下,逆置一单链表。
算法思路:
      逆置后的点链表初始为空,表中的节点不是新生成的,而是从原链表当中一次“删除”,再逐个头插到逆置表中。设逆置链表的初始态为空表,“删除”已知链表中的第一个节点,然后将它“插入”到逆置链表的“表头”,即使得他成为逆置链表中“新”的第一个节点,如此循环,直至原链表为空。

假设有如下数据结构:
  1. #define ElemType char

  2. typedef struct Node{
  3.     ElemType data;
  4.     struct Node *next;
  5. }Node,*LinkList;

如下图所示:

代码如下:
  1. void ReverseList(LinkList L)
  2. {
  3.     Node *p,*q;
  4.     p = L->next;             /*p为原链表的当前处理节点*/
  5.     L->next = NULL;          /*逆置单链表初始为空*/
  6.     
  7.     while(p != NULL){        /*当原链表未处理完*/
  8.         q = p->next;         /*q指针保留原链表当前处理节点的下一个节点*/
  9.         p->next = L->next;   /*将当前处理节点p插入到逆置L的表头*/
  10.         L->next = p;
  11.         p = q;               /*p指向下一个待插入的节点*/
  12.     }
  13. }
其实也比较简单;就是有点绕。
同时给出头插法建立链表的代码:
  1. void CreatList(LinkList L)
  2. {
  3.     Node *s;
  4.     char c;
  5.     int flag = 1;
  6.     while(flag){
  7.         c = getchar();
  8.         if(c != '$'){
  9.             s = (Node*)malloc(sizeof(Node));
  10.             s->data = c;
  11.             s->next = L->next;
  12.             L->next = s;
  13.         }else
  14.             flag = 0;
  15.     }
  16. }
其实这仅仅是两个部分,现在给出笔者再ubuntu下的运行结果:

下载代码: ReverseList.txt   


阅读(1787) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~