2017-09-18 21:15:38
writer：pprp
报告如下：
数据结构第三次作业 - 链表的逆置
问题：
编写算法，实现单链表的原地逆置操作（原地逆置即不需要新开辟空间）。单链表带有头结点，指针first指向头结点,List类以及定义节点的LinkNode类定义同课本。不需要编写能运行的程序，写出算法即可，函数的声明已给出，只需要写出函数体。
解题思路：
构造一个新的头节点，将原来的链表的元素连到新的头结点，采用头插法的方式，最后将first指针指向新的头结点完成链表的逆置。
主要的函数体：
template <class T>
void List<T>::inverse()
{
if(first == NULL||first->next == NULL)//判断是否为空表
return ;
LinkNode<T>*head, *p;//声明了两个指针head用来构造新的一段链表，p用来遍历原先的链表
head = NULL;
first = first->next;
p = first;
while(p != NULL)//循环找到新的节点，采用头查的方法将该节点连到head上，最终达到逆置效果
{
p = p->next;
first->next = head;
head = first;
first = p;
}
first = new LinkNode<T>;
first->next = head;
Head = p = NULL;
}
说明：
对带有头结点的链表进行操作的，由于input和output函数都是根据带有头结点的链表而写的，所以会有一些不太一样的地方，具体分析见代码。
测试结果：
input the size:
10
please enter the element:
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
Process returned 0 (0x0) execution time : 8.237 s
Press any key to continue.
完整代码见：https://github.com/pprp/personal/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%AC%AC%E4%B8%89%E6%AC%A1%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BD%9C%E4%B8%9A%20-%20%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0%E9%80%86%E7%BD%AE.cpp