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

yunin

与大家讨论，下面是我的实现，请大家斧正。
（随机测试，最大最至20000，都能有正确的结果）


#include <stdio.h>;
#include <stdlib.h>;

#define SWAP(a,b) { \
        a=a^0xFFFFFFFF; \
        b=b^a; \
        a=a^b; \
        b=b^0xFFFFFFFF; \
        b=b^a; \
        }
#define SWAP_POINT(pA,pB) {\
        int h,t; \
        pLinkList ph,pt; \
        h=(int)pA; \
        t=(int)pB; \
        ph = (pLinkList)h; \
        pt = (pLinkList)t; \
        SWAP(h,t); \
        pA = (pLinkList)h; \
        pB = (pLinkList)t; \
        }

typedef struct tagLinkList
{
        int data;
        struct tagLinkList *next;
} LinkList , *pLinkList ;


int main(int argc, char* argv[])
{
        int count,i;
        pLinkList Head,tmpNode,Tail;
       
        Head=NULL;
       
        // Construct LinkList.
        printf("Enter count:"; scanf("%d",&count);
        if(count <= 1)
        {
                printf("Count error,must large than 1.\n";
                exit(1);
        }
        for(i=1;i<=count;++i)
        {
                tmpNode=(LinkList *)malloc(sizeof(LinkList));
                tmpNode->;data=i;
                printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->;data);
                if(!Head)
                        Tail=Head=tmpNode;
               
                else{
                        Tail->;next=tmpNode;
                        Tail=tmpNode;
                }
        }
        Tail->;next=NULL;
       
        // Reverse LinkList.
        if(2 == count) {
                //N=2
                SWAP_POINT(Head,Tail->;next);
                SWAP_POINT(Head,Tail);
                SWAP_POINT(Head->;next->;next,Tail);
        }else if(3 == count) {
                //N=3
                SWAP_POINT(Head->;next,Tail->;next);
                SWAP_POINT(Head,Tail);
                SWAP_POINT(Head->;next->;next,Tail);
        }else{
                //N>;=4
                SWAP_POINT(Head->;next,Tail->;next);
                SWAP_POINT(Head,Tail);
                SWAP_POINT(Head->;next->;next,Tail);
                SWAP_POINT(Head->;next,Tail->;next);
                SWAP_POINT(Head->;next->;next,Tail);
                for(i=6;i<=count;++i)
                {
                        SWAP_POINT(Head->;next,Tail);
                        SWAP_POINT(Head->;next->;next,Tail);
                }
        }
       
        //Output reversed LinkList.
        tmpNode=Head;
        printf("After reverse.\n";
        for(i=1;i<=count;++i)
        {
                printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->;data);
                tmpNode = tmpNode->;next;
        }
       
        //Release LinkList
        printf("Release LinkList.\n";
        for(i=1;i<=count;++i)
        {
                tmpNode=Head;
                Head = Head->;next;
                free(tmpNode);
        }

        return 0;
}

yunin

今天早上起来想了想，由于语言的问题，在类型转换时还是使用了辅助指针及int临时变量。没有完全达到楼主的要求，思索再三，要想完全不再多用辅助变量，只能借助于块汇编了，避开类型转换时需要中间变量。

改了三处，如下所示。欢迎大家讨论。

1. 
   
2. #include <stdio.h>;
   
3. #include <stdlib.h>;
   
4. 
   
5. #define SWAP(a,b) { \
   
6.         a=a^0xFFFFFFFF; \
   
7.         b=b^a; \
   
8.         a=a^b; \
   
9.         b=b^0xFFFFFFFF; \
   
10.         b=b^a; \
    
11.         }
    
12. #define SWAP_POINT(pA,pB) {\
    
13.         int h,t; \
    
14.         pLinkList ph,pt; \
    
15.         h=(int)pA; \
    
16.         t=(int)pB; \
    
17.         ph = (pLinkList)h; \
    
18.         pt = (pLinkList)t; \
    
19.         SWAP(h,t); \
    
20.         pA = (pLinkList)h; \
    
21.         pB = (pLinkList)t; \
    
22.         }
    
23. 
    
24. typedef struct tagLinkList
    
25. {
    
26.         int data;
    
27.         struct tagLinkList *next;
    
28. } LinkList , *pLinkList ;
    
29. 
    
30. 
    
31. int main(int argc, char* argv[])
    
32. {
    
33.         int count,i;
    
34.         pLinkList Head,tmpNode,Tail;
    
35.        
    
36.         Head=NULL;
    
37.        
    
38.         // Construct LinkList.
    
39.         printf("Enter count:"); scanf("%d",&count);
    
40.         if(count <= 1)
    
41.         {
    
42.                 printf("Count error,must large than 1.\n");
    
43.                 exit(1);
    
44.         }
    
45.         for(i=1;i<=count;++i)
    
46.         {
    
47.                 tmpNode=(LinkList *)malloc(sizeof(LinkList));
    
48.                 tmpNode->;data=i;
    
49.                 printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->;data);
    
50.                 if(!Head)
    
51.                         Tail=Head=tmpNode;
    
52.                
    
53.                 else{
    
54.                         Tail->;next=tmpNode;
    
55.                         Tail=tmpNode;
    
56.                 }
    
57.         }
    
58.         Tail->;next=NULL;
    
59.        
    
60.         // Reverse LinkList.
    
61.         if(2 == count) {
    
62.                 //N=2
    
63.                 //SWAP_POINT(Head,Tail->;next);
    
64.                 _asm {        
    
65.                         mov eax,DWORD PTR Head
    
66.                         mov edx,DWORD PTR Tail
    
67.                         mov esi,4
    
68.                         mov ebx,[edx][esi]
    
69.                         xor ebx,eax
    
70.                         xor eax,ebx
    
71.                         xor ebx,eax
    
72.                         mov Head,eax
    
73.                         mov [edx][esi],ebx
    
74.                 }
    
75.                 SWAP_POINT(Head,Tail);
    
76.                 SWAP_POINT(Head->;next->;next,Tail);
    
77.         }else if(3 == count) {
    
78.                 //N=3
    
79.                 SWAP_POINT(Head->;next,Tail->;next);
    
80.                 SWAP_POINT(Head,Tail);
    
81.                 SWAP_POINT(Head->;next->;next,Tail);
    
82.         }else{
    
83.                 //N>;=4
    
84.                 SWAP_POINT(Head->;next,Tail->;next);
    
85.                 SWAP_POINT(Head,Tail);
    
86.                 SWAP_POINT(Head->;next->;next,Tail);
    
87.                 SWAP_POINT(Head->;next,Tail->;next);
    
88.                 SWAP_POINT(Head->;next->;next,Tail);
    
89. 
    
90.                 _asm{
    
91.                         mov ebx,DWORD PTR Tail
    
92.                         mov esi,4
    
93.                 }
    
94.                 for(i=6;i<=count;++i)
    
95.                 {
    
96.                         //SWAP_POINT(Head->;next,Tail);
    
97.                         _asm {        
    
98.                                 mov edx,DWORD PTR Head
    
99.                                 //mov ebx,DWORD PTR Tail
    
100.                                 //mov esi,4
     
101.                                 mov eax,[edx][esi]
     
102.                                 xor ebx,eax
     
103.                                 xor eax,ebx
     
104.                                 xor ebx,eax
     
105.                                 //mov Tail,ebx
     
106.                                 mov [edx][esi],eax
     
107.                         }
     
108.                         //SWAP_POINT(Head->;next->;next,Tail);
     
109.                         _asm {        
     
110.                                 mov eax,DWORD PTR Head
     
111.                                 //mov ebx,DWORD PTR Tail
     
112.                                 //mov esi,4
     
113.                                 mov edx,[edx][esi]
     
114.                                 mov eax,[edx][esi]
     
115.                                 xor ebx,eax
     
116.                                 xor eax,ebx
     
117.                                 xor ebx,eax
     
118.                                 //mov Tail,ebx
     
119.                                 mov [edx][esi],eax
     
120.                         }
     
121.                 }
     
122.         }
     
123.        
     
124.         //Output reversed LinkList.
     
125.         tmpNode=Head;
     
126.         printf("After reverse.\n");
     
127.         for(i=1;i<=count;++i)
     
128.         {
     
129.                 printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->;data);
     
130.                 tmpNode = tmpNode->;next;
     
131.         }
     
132.         printf("Tail->;data = %d\n",Tail->;data);
     
133.         //Release LinkList
     
134.         printf("Release LinkList.\n");
     
135.         for(i=1;i<=count;++i)
     
136.         {
     
137.                 tmpNode=Head;
     
138.                 Head = Head->;next;
     
139.                 free(tmpNode);
     
140.         }
     
141. 
     
142.         return 0;
     
143. }
     

复制代码

sososue

原帖由 "释雪" 发表：
还是不明白不使用辅助节点的意思...
使用指针变量应该不算是辅助节点吧.
前提 尾节点的next=NULL.

Node_t* reverse(Node_t* pNode, Node_t* pPrev)
{
　　Node_t *pNext;
　　pNext = pNode->;next;
　　..........

不错呀！
很棒，正好在写这个代码，帮了大忙呀！谢谢哦！

FH

嗯！寄存器可绝对不是C里面的这指针那指针了，嘿嘿
俺不赞成用汇编，没有可移植性。
又不是系统核心里的底层硬件操作，有必要汇编么？

yunin

我将N的情况分成了，N=2，N=3，N>;=4（其实是N=4,5与N>;=6）几种情况，我一直希望有人能将这几种情况统一起来。

我觉得我提供的代码应该满足了楼主的要求，不用辅助结点，只是感觉用了列举N的方法，不是太统一。

yunin

原帖由 "FH" 发表：
嗯！寄存器可绝对不是C里面的这指针那指针了，嘿嘿
俺不赞成用汇编，没有可移植性。
又不是系统核心里的底层硬件操作，有必要汇编么？

如果你可以将地址转换成整数时能不用辅助变量变就可以不必要用啊。

我给出汇编，只是说明我C实现时用的辅助变量的原因。而且，汇编的效率高了许多，时间复杂度做到了O(n)。

前面所有给出的解决办法，好像都不全符合楼主的要求，除了汇编的办法外。

converse

越来越偏了吧?汇编都用上了,数据结构的学习要求学生掌握的是什么?其实楼主不用辅助结点的条件本身就有待商榷.如果我是老师，学生交上来一个用汇编写的代码即便是效率很高但是算法和数据结构的选择有问题，我照样不会给高分的，甚至可能不给他及格。

cattiger

1.                
   
2.                 for(i=0;phead!=NULL;phead=phead->;next,i++)
   
3.                 {
   
4.                         sprintf(temp,"%d",phead);比较笨，取得地址，存入数组
   
5.                         add[i]=atoi(temp);
   
6.                 }
   
7. 
   
8.      phead=(struct ListNode *)add[i-1];
   
9.                 for(j=0;j<i-1;j++）
   
10.                 {
    
11.                         phead->;next = (struct ListNode *)add[i-2-j];
    
12.                         phead=phead->;next;
    
13.                 }
    
14. 
    
15.                 phead->;next=NULL;
    
16.      phead=(struct ListNode *)add[i-1];
    
17.       return phead;

复制代码

phead为链表头，总该给把!用几个变量没有违规吧！

yunin

[quote]原帖由 "converse"]越来越偏了吧?汇编都用上了,数据结构的学习要求学生掌握的是什么?其实楼主不用辅助结点的条件本身就有待商榷.如果我是老师，学生交上来一个用汇编写的代码即便是效率很高但是算法和数据结构的选择有问题，我照样不会..........[/quote 发表：


唉，converse，你都没有看清楼主的要求，就说是别人的老师什么的，太过牵强了。

我之所以出手回答楼主这个看似简单、无聊的问题，其实是有些价值及意义的。

对于我现在做的视频压缩方面的东西，楼主的贴子还真给了我少许的启示，将我发现的算法应用到了我的开发之中，特别是后面的汇编代码，我也用到实际的项目之中去了（你可能不知道，许多的代码还要用到SSE/SSE2的来优化）。

既然来自楼主的启示，当然我也得回报于这个坛子。楼主的限制，真是给一些有苛刻要求的应用有少许参考。

还是请converse多将眼光放宽些再去评价楼主的要求及众人给出的答案，而且也要有勇气去承认别人的做法比你的有见地。

就算你是老师，如果符合题目要求的答案你说不好，拿你自己不符合要求的答案说是对的，恐怕也不是为师之“道”，也不符合楼主提出的“游戏规则”。

如果你觉得我写的代码不好，就请给出个好的代码来。别光说不练。当然，也请别笑话我，大家探讨，不必上气，会有失程序之“道”的。

converse

不是，我没有说你的程序写的不好，其实我之前并没有看过，不好评论，我只是觉得似乎考虑这个问题的思路越来越偏，不要忘了楼主刚开始学习数据结构，正常情况下，老师给出的任何一个有关数据结构的题目都是要考察学生对基本的数据结构和算法的理解，不会出一个非得要汇编才能解决的问题，所以我担心往这个方向考虑会让楼主在刚开始学习数据结构的时候就走错方向－－考虑一个问题的时候，首先不是从数学角度考虑怎么设计和选择数据结构和算法的，而是首先从机器角度考虑的。我上面说的“如果我是老师”等等之类的话也不是我要做别人的老师，事实上我也不够格，只是我从作为教授数据结构老师的角度出发考虑的希望学生从数据结构的学习里应该学到的是什么。
    当然，你上面提到了你的工作用到了这里的东东，这是我没有考虑到的，这么看来的话我倒是蛮佩服你的钻研精神的，这个问题我目前也想不到其他别的什么办法了，我指的是数学上的，所以也给不出别的好办法来了。
    以上文字是对我的相应言论进行解释的，如果有过激的地方我道歉，还请大家原谅！
    最后，就事论事吧，我看了看yunin的代码，我知道我们之间最大的分歧在哪里了，可能你做底层的程序多了吧，汇编玩的熟了，所以考虑一个问题的时候首先从机器角度出发的；我反之，我首先是从数学角度出发看看这个问题应该如何选择和设计数据结构和算法，然后再从机器的角度出发考虑程序的优化，因为我觉得机器在变，解决问题的思路不会有太大的变化。
    难得有个有点意思的问题大家一起讨论，我想yunin，FH等人都做到了足够的心平气和了，事实上有分歧才会产生火花，思想的碰撞才能互相进步，继续保持对这个问题的关注！