谁能贴个最全的单链表就地就逆转算法？

sunchiang

普通的，递归的，还有没有其他的？

MMMIX

原帖由 sunchiang 于 2008-5-26 09:45 发表
普通的，递归的，还有没有其他的？

你会实现几种？

sunchiang

原帖由 MMMIX 于 2008-5-26 21:43 发表

你会实现几种？

我就是在这个问题上绕不清楚，哪位高手指点一下？

Cyberman.Wu

你的题目有些不清楚，是链表反序吗？反正要临时指针，做一个临时的头，把单向链表看做一个栈就很容易做出来了。

sunchiang

原帖由 Cyberman.Wu 于 2008-5-29 09:29 发表
你的题目有些不清楚，是链表反序吗？反正要临时指针，做一个临时的头，把单向链表看做一个栈就很容易做出来了。

你的意思是先把链表节点入栈然后再出栈形成新链表么？似乎不满足“就地”条件啊。肯定是需要临时变量的，有没有具体算法给贴几个？

swordfish.cn

原地反转

1. 
   
2. Node * reverse(Node *list)
   
3. {
   
4.     Node *p = list, *q = NULL, *r;
   
5.     while (p) {
   
6.         r = p->next;
   
7.         p->next = q;
   
8.         q = p; p = r;
   
9.     }
   
10.     return p;
    
11. }
    

复制代码

Cyberman.Wu

原帖由 sunchiang 于 2008-6-11 15:32 发表


你的意思是先把链表节点入栈然后再出栈形成新链表么？似乎不满足“就地”条件啊。肯定是需要临时变量的，有没有具体算法给贴几个？

“栈”是指一种思路，不是非要用什么特殊的数据结构：

void reverse(Node **head) {     Node *old_head = *head;     Node *new_head = NULL;     while (old_head)     {         Node *tmp = old_nead;         old_head = old_head->next;         tmp->next = new_head;         new_head = tmp;     }     *head = new_head; }

每次从旧链表的头部取一个节点，然后插入到新链表的头部，实际上就相当于一个出栈和一个入栈。

Cyberman.Wu

刚发现和楼上的方法实际上是一样的，呵呵。许多人做这个问题总是想着再指向next的next，导致还要处理只有一个节点的特殊情况。

sunchiang

谢谢LS的兄弟们：）