[C++知识库][C语言、C++]数据结构作业：在带头结点的单链表基础上，完成单链表原地逆序的函数。

在带头结点的单链表基础上，完成单链表原地逆序的函数。

函数输入为一个含有多个数据结点的带头单链表，运行函数后，该单链表已经原地逆序了。

函数头：

ReverseList(const LinkList &L)

函数自行实现。

方法1（10分）：将原链表L分成两部分，头，以及剩余链表，将剩余链表中的结点用头插法依次插入到头中。

====main中测试：

1、利用头插形成一个元素为5,4,3,2,1的带头单链表

2、遍历打印

3、利用逆序函数将该单链表逆序

4、遍历打印

方法2（附加，5分）：原地逆序，函数名：ReverseList2(const LinkList &L)，测试可用同样代码。

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	LinkNode* next;
}*LinkList;
void InitLinkList(LinkList& L) {
	LinkNode* s = new LinkNode;
	s->next = NULL;
	L = s;
}
void Traverse(const LinkList& L) {
	LinkNode* p = L->next;
	while (p) {
		cout << p->data << endl;
		p = p->next;
	}
}
void CreatHead(LinkList& L, int n) {
	L = new LinkNode; L->next = NULL;
	for (int i = 0; i < n; i++) {
		LinkNode* s = new LinkNode;
		cin >> s->data;
		s->next = L->next;
		L->next = s;
	}
}
void ReverseList(LinkList& L) {
	LinkNode* p=L->next;
	LinkList LB;
	InitLinkList(LB);
	while (p) {
		LinkNode* s = p->next;
		p->next = LB->next;
		LB->next = p;
		p = s;
	}
	L->next=LB->next;
}
void ReverseList2(LinkList& L) {
	LinkNode* p = L->next;
	LinkNode* q = p->next;
	while (q) {
		p->next = q->next;
		q->next = L->next;
		L->next = q;
		q = p->next;
	}
}
int main(){
	LinkList L;
	InitLinkList(L);
	CreatHead(L, 5);
	Traverse(L);
	cout << "================第一次逆序完成===========================" << endl;
	ReverseList(L);//第一种逆序函数
	Traverse(L);//逆序后打印出：1，2，3，4，5
	cout << "================第二次逆序完成===========================" << endl;
	ReverseList2(L);
	Traverse(L);
}

Tips:由于这里逆序的操作只用到了单链表的初始化，遍历，和头插操作，所以代码段中不在赘述其他操作，详情见[C语言、C++]数据结构作业：线性表-单链表(带头节点)的部分基本操作和[C语言、C++]数据结构作业：线性表-单链表(带头节点)的剩余基本操作(接上一张基本操作)