【Weiss】【第03章】练习3.12：单链表倒置

【练习3.12】

a.编写一个非递归过程以O(N)时间反转单链表。

b.使用常数附加空间编写一个过程以O(N)时间反转单链表。

Answer:

这题的b貌似没啥意义，在a小题里直接用头插法，不断地将头节点后移，

并将当前头节点所在的节点的后继指针指回前驱就能倒置链表了，不需要额外的空间。

所以就写了a。

测试代码：

 1 #include <iostream>
 2 #include "linklist.h"
 3 using namespace std;
 4 using namespace linklist;
 5 template class List<int>;
 6 int main(void)
 7 {
 8     List<int> number;
 9 
10     //测试插入
11     cout << "/*additem()*/" << endl;
12     number.additem(2);
13     number.additem(3);
14     number.additem(5);
15     number.additem(7);
16     number.additem(11);
17     number.traverse();
18     cout << "
/*end*/

" << flush;
19 
20     number.reverse();
21 
22     number.traverse();
23 
24     system("pause");
25 }

View Code

倒置链表代码：

 1 //练习3.12新增，倒置单链表
 2 template <typename T> void List<T>::reverse()
 3 {
 4     if (length != 0)
 5     {
 6         Node<T>* curr = rear = front;
 7         Node<T>* prev = nullptr;
 8         while (front->next != nullptr)
 9         {
10             front = front->next;
11             //此时curr和prev分别为front前一个及前两个节点
12             //改变curr使其反向指向原前驱
13             curr->next = prev;
14             //指针后移
15             prev = curr;
16             curr = front;    
17         }
18         front->next = prev;
19     }
20 }