Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8099268
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14615
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: C/C++

2011-08-14 19:44:05

本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
作者:gfree.wind@gmail.com
博客:linuxfocus.blog.chinaunix.net

这又是一道比较俗的题目,但是却经常可以见到。今天想到这道题,虽然知道如何解决,但是把代码完全写好,并调试验证,居然也花了20分钟。看来真的需要好好巩固巩固这些基础知识和算法了。

好,下面回到正题。
单链表的节点,只有一个指针指向下一个节点,那么如果要倒转单链表,如何解决呢?
下面的解决方法,即以swap两个变量的思想,对于链表来说,即使用三个临时指针,来交换指针地址,实现一次遍历单链表,即完成单链表倒转的工作。

  1. struct list_node {
  2.     struct list_node *next;
  3.     void *data;
  4. };

  5. /*
  6. 该函数用于倒转单链表
  7. 参数:head为输入的单链表头指针;
  8. 返回值为:倒转后的单链表的头指针;
  9. */
  10. struct list_node *reverse_list(struct list_node *head)
  11. {
  12.     /* 检查是否为指针是否有效 */
  13.     if (!head) {
  14.         return NULL;
  15.     }

     /* 初始化三个临时指针 */
  1.     struct list_node *p1, *p2, *p3;
  2.     p1 = head;
  3.     p2 = p3 = NULL;

     /* 遍历该单链表,并利用三个临时指针,对单链表的节点的next进行交换 */
  1.     while (p1->next) {
  2.         p2 = p1->next;
  3.         p1->next = p3;

  4.         if (!p2->next) {
  5.             p2->next = p1;
  6.             return p2;
  7.         }
  8.         p3 = p2->next;
  9.         p2->next = p1;

  10.         if (!p3->next) {
  11.             p3->next = p2;
  12.             return p3;
  13.         }
  14.         p1 = p3->next;
  15.         p3->next = p2;
  16.     }
  17.     p1->next = p3;
  18.     
  19.     return p1;
  20. }
这个函数的代码我写得一般,感觉好像还可以把代码再优化一下,更简洁一些。我就不做这个工作了,抛砖引玉了,望大家指正。


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

shevarey2011-08-17 15:48:11

LZ,你这个太麻烦了啊。我写了个:

struct node* reverse(struct node *head){
        struct node *p, *q, *r;
        p = NULL;
        q = head;
        while(q){
                r = q->next;
                q->next = p;
                p = q;

GFree_Wind2011-08-15 22:33:02

Bean_lee: 兄弟下手够快啊,估计明天我就看到单链表环检测的代码了。呵呵.....
呵呵,写完单链表检测循环的代码了。。。这个实现起来比较简单

GFree_Wind2011-08-14 22:53:15

Bean_lee: 兄弟下手够快啊,估计明天我就看到单链表环检测的代码了。呵呵.....
呵呵,很有可能哈。。。。
本来还不知道,明天写个什么练手呢。。。正好你提醒呵

Bean_lee2011-08-14 22:01:52

兄弟下手够快啊,估计明天我就看到单链表环检测的代码了。呵呵