如何实现一个单链表的反转?

wg0124

使用堆栈也需要消耗空间的，最起码要消耗如下的单元：
int i;    用于交换队列数据的空间。
链表 *p;  用于指向当前链表单元。
使用指针，需要消耗如下的空间：
链表 *p1,*p2,*p3;  其中p1，p3均用来指向当前处理的链表节点，p2用来指
                      向上个节点。
至于算法的复杂度我不是很清楚，我只知道使用堆栈要遍历(n-1)次链表，使用指针要遍历1次链表。
以下是俺测试用的使用指针的小程序，测试过（TC2.0）：
#include "stdio.h"

struct Link_Tab
{
  int dat;
  struct Link_Tab * next_nod;
}My_Link[5],*p,*q,*p1;

main()
{
  int i;

  //初始化链表（5节点）
  for(i=0;i<6;i++)
  {
    switch(i)
    {
      case 4:
        My_Link.dat=i;
        My_Link.next_nod=NULL;
        break;
      case 5:
        break;
      default:
        My_Link.dat=i;
        My_Link.next_nod=&My_Link[i+1];
        break;
    }
  }

//反序
  p=&My_Link[0];
  q=NULL;
  do
  {
    p1=(*p).next_nod;
    (*p).next_nod=q;
    q=p;
    p=p1;
  }while(p!=NULL);

//打印输出链表数据
  while(q!=NULL)
  {
    printf("%d\n",(*q).dat);
    q=(*q).next_nod;
  }

qingfeng18

我没有测试，可以用宏定义实现。

typedef data int;
typedef struct list_node {
   list_node *next;
   data elem;
}list_node， *p_list_node;


void reverse_list (p_list_node *pp_head, p_list_node p_pre, p_list_node p_this)
{
        if (NULL == p_pre || NULL == p_this)
                return;
        else if(NULL == p_this->;next)
        {
                p_this->;next = p_pre;
                *pp_head = p_this;
        }
        else
                reverse_list(pp_head, p_this, p_this->;next);
}


/* 调用处 */
reverse_list(&phead, phead, phead);

qingfeng18

用宏定义的话不算是中间辅助节点吧，事件复杂度？O(n)
那位可以帮忙测一下
有一点改动

#define reverse_list (pp_head,  p_pre,  p_this)  \
{\
if (NULL == p_pre || NULL == p_this)\
*pp_head = NULL;\
else if(NULL == p_this->;next)\
{\
p_this->;next = p_pre;\
*pp_head = p_this;\
}\
else\
reverse_list(pp_head, p_this, p_this->;next);\
}

qingfeng18

前面的代码有错误,宏定义有问题,不能递归,不好意思,晕了.
我用递归函数实现不知是否符合要求.

附带相关源码:
#include <stdio.h>;
#include <stdlib.h>;

typedef struct list_node {
struct list_node *next;
int number;
}list_node, *p_list_node;

void reverse_list (p_list_node *pp_head, p_list_node p_pre, p_list_node p_this)
{
        if (NULL == p_this)
                *pp_head = NULL;
        else if(NULL == p_this->;next)
        {
                p_this->;next = p_pre;
                *pp_head = p_this;
        }
        else
        {
                reverse_list(pp_head, p_this, p_this->;next);
                p_this->;next = p_pre;
        }
}

p_list_node mk_list()
{
        int i = 0;
        p_list_node tmp_node = NULL;
        p_list_node this_node = NULL;

        for(;i < 10;i++)
        {
                tmp_node = calloc (sizeof(list_node), 1);
                tmp_node->;number = i;
                tmp_node->;next = this_node;
                this_node = tmp_node;
        }

        return this_node;
}

void print_list (p_list_node p_head)
{
        p_list_node p_this = NULL;
        if (NULL == p_head)
                printf("The list is NULL!";
        else
                for (p_this = p_head; NULL != p_this; p_this = p_this->;next)
                        printf("The node addr is [%lu],\tThe node data is [%d].\n", p_this, p_this->;number);
}

void free_list (p_list_node p_head)
{
        p_list_node p_this = p_head;
        p_list_node p_tmp = NULL;

        for (; NULL != p_this; p_this = p_tmp)
        {
                p_tmp = p_this->;next;
                free (p_this);
        }
}

int main (int argc, char *argv[])
{
        p_list_node p_head = mk_list();

        printf("\nNow printf the info before reverse!\n";
        print_list (p_head);

        /* reverse_list */
        reverse_list((&p_head), NULL, p_head);

        printf("\nNow printf the info after reverse!\n";
        print_list (p_head);
        free_list (p_head);
        p_head = NULL;       
}


linux下gcc编译运行结果:

Now printf the info before reverse!
The node addr is [134519176],        The node data is [9].
The node addr is [134519160],        The node data is [8].
The node addr is [134519144],        The node data is [7].
The node addr is [134519128],        The node data is [6].
The node addr is [134519112],        The node data is [5].
The node addr is [134519096],        The node data is [4].
The node addr is [134519080],        The node data is [3].
The node addr is [134519064],        The node data is [2].
The node addr is [134519048],        The node data is [1].
The node addr is [134519032],        The node data is [0].

Now printf the info after reverse!
The node addr is [134519032],        The node data is [0].
The node addr is [134519048],        The node data is [1].
The node addr is [134519064],        The node data is [2].
The node addr is [134519080],        The node data is [3].
The node addr is [134519096],        The node data is [4].
The node addr is [134519112],        The node data is [5].
The node addr is [134519128],        The node data is [6].
The node addr is [134519144],        The node data is [7].
The node addr is [134519160],        The node data is [8].
The node addr is [134519176],        The node data is [9].

flw

你们都在讨论什么啊？

Moonwellatg4

已经偏离了追求效率或者节省空间的目标了。

FH

原帖由 "wg0124" 发表：

使用堆栈也需要消耗空间的，最起码要消耗如下的单元：
int i; 用于交换队列数据的空间。
链表 *p; 用于指向当前链表单元。
使用指针，需要消耗如下的空间：
链表 *p1,*p2,*p3; 其中p1，p3均用来指向当前处理的链表节点，p2用来指
向上个节点。
至于算法的复杂度我不是很清楚，我只知道使用堆栈要遍历(n-1)次链表，使用指针要遍历1次链表。

错误满天飞，俺只有苦笑了。

流川

昨晚刚好做了这一题,我再做一遍!

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. typedef struct NODE
   
4. {
   
5.         int data;
   
6.         struct NODE *next;
   
7. }NODE;
   
8. 
   
9. NODE *f(NODE  *head);
   
10. int main(void)
    
11. {
    
12.         int n,i;
    
13.         NODE *head,*p,*q;
    
14. 
    
15.         head=NULL;
    
16. 
    
17.         printf("Enter n:"); scanf("%d",&n);
    
18.         for(i=1;i<=n;i++)
    
19.         {
    
20.                 p=(NODE *)malloc(sizeof(NODE));
    
21.                 p->;data=i;
    
22.                 if(head==NULL)
    
23.                         q=head=p;
    
24. 
    
25.                 else{
    
26.                         q->;next=p;
    
27.                         q=p;
    
28.                 }
    
29.         }
    
30.         q->;next=NULL;
    
31. 
    
32.         for(p=head;p;p=p->;next)
    
33.                 printf("%4d",p->;data);
    
34.         printf("\n逆顺输出:");
    
35.         for(p=f(head);p;p=p->;next)
    
36.                 printf("%4d",p->;data);
    
37.         return 0;
    
38. }
    
39. 
    
40. NODE *f(NODE  *head)
    
41. {
    
42.      NODE *p,*q;
    
43.      NODE *h;
    
44. 
    
45.     h=NULL;
    
46.    for(q=head,p=head->;next;p;q=p,p=p->;next)//p指向head->;next直到链表为空!
    
47.   {
    
48.      if(h==NULL){
    
49.         h=q;
    
50.         h->;next=NULL;
    
51.       }
    
52.    else{
    
53.        q->;next=h;
    
54.        h=q;
    
55.        }
    
56.    }
    
57.    q->;next=h;
    
58.    h=q;
    
59.   
    
60.    return h;
    
61. }

复制代码

//ok,搞定!

FH

while(q=head,p=head->;next;p;q=p,p=p->;next)
这句不太懂，就是那个"p;"是什么意思啊？

流川

楼上的,我把for写成while了,呵呵

我的代码,没有什么问题的!
昨天有人说我的代码让人看了吓一跳!
我很纳闷,测试结果如下:

Enter n:10
   1   2   3   4   5   6   7   8   9  10
逆顺输出:  10   9   8   7   6   5   4   3   2   1