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

aero

不使用辅助结点是什么意思？

FreeGnu

修改节点指针不就OK了

assiss

不使用任何辅助节点?
那可能吗?
起码要一两个指针吧

converse

可以这样做，比如一个链表是这样的： 1->;2->;3->;4->;5
第一次，取出1并且把它从链表中删除，然后把它作为新链表的第一个元素。
第二次，取出2并且把它从链表中删除，在新链表中2的下一个元素是1，即在第二次操作之后新旧链表
分别是：旧链表 3->;4->;5 新链表 2->;1
依此类推，这样在一次遍历旧链表就可以完成链表的逆转，不需要其他的指针（就是辅助结点），
复杂度与链表长度成正比，为O(N)。

converse

1. 
   
2. typedef data int;
   
3. 
   
4. typedef struct ListNode {
   
5.         ListNode *next;
   
6.         data elem;
   
7. }ListNode， *pListNode;
   
8. 
   
9. pListNode reverse_list(pListNode list)
   
10. {
    
11.         assert(list);
    
12.        
    
13.         pListNode p, q, s;       
    
14.        
    
15.         /*
    
16.                 循环中，p指向旧链表的第一个结点，q指向新链表的第一个结点，
    
17.                 p不断的向后走直到遍历完旧链表，而q不断的前移。
    
18.         */
    
19.         for (p = list, q = NULL; NULL != p ;p = s) {       
    
20.                 s = p->;next; /* 保存旧链表的下一个结点 */
    
21.                 p->;next = q; /* 把一个结点从旧链表断开并变成新链表的第一个结点 */
    
22.                 q = p;             /* q指针前移 */
    
23.                 p = s;             /* p指针后移 */
    
24.         }
    
25.        
    
26.         return q;
    
27. }

复制代码

aero

原帖由 "GAORJ" 发表：
请教在不用辅助节点的情况下如何修改链表节点的指针使其反转指向???

辅助节点是指用来存储链表节点指针的临时节点变量!希望我说清楚了我的意思。

诚心恳求解答！谢谢

这句话，真的不懂。结点指针是指针，存放的是地址。结点变量是存放的结点内容。你这句话，到底是什么意思呢？

assiss

楼上的楼上,你还是用了""辅助节点""啊.呵呵.
楼主的要求很奇怪.是不是变态老师出的变态题目啊?

FH

原帖由 "GAORJ" 发表：
辅助节点是指用来存储链表节点指针的临时节点变量!希望我说清楚了我的意思。

[quote]原帖由 "converse"]pListNode p, q, s;[/quote 发表：