用C++实现单链表的创建、逆置和输出 的两种方法
http://blog.****.net/lfeng_coding/article/details/47300563
题目描述:在已知单链表头节点的情况下,设计算法逆置单链表并输出
方法一:采用首先将头节点指向空,让其变为尾节点,然后利用中间节点 p、q 将其后的节点一个接一个改为指向前面的节点
/****************************
*作者:刘峰
* 时间:2015\8\5
* 环境:VS2013
* 功能:实现创建一个节点可控的单链,并逆置输出
****************************/
- #include "stdafx.h"
- #include <iostream>
- using namespace std;
- struct List
- {
- int num;
- List *next;
- };
- List *createList(int n) //创建含有n个节点的单链表
- {
- List *head, *p, *q;
- q=head = NULL; //初始化表头和中间指针
- int i;
- for (i = n; i > 0; --i)
- {
- p = new List; //申请空间,创建第一个节点
- cin >> p->num; //往节点中存入数据信息
- if (head == NULL)
- {
- head = p;
- }
- else
- {
- q->next = p;
- }
- q = p;
- }
- q->next = NULL;
- return head;
- }
- List *ReverseList(List *head) //逆置单链表
- {
- List *p, *r; //定义两个中间节点,用于顺移逆置链表节点
- if (head->next == NULL)
- return head;
- p = head; //获取头节点地址
- r = p->next; //获取链表第二个节点地址
- p->next = NULL; //头节点变为尾节点,原链表表头指向空
- while (r)
- {
- p = r;
- r = r->next;
- p ->next = head; //使第二个节点指向原先的头节点
- head = p; //使第二个节点变为头节点,用于循环逆置
- }
- return head;
- }
- void print(List *head) //输出逆置后的单链表
- {
- List *p;
- p = head;
- while (p)
- {
- cout<<p->num;
- p = p->next;
- cout << " ";
- }
- cout << endl;
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- List *p, *q;
- cout << "请输入单链表的节点个数:";
- int n;
- cin >> n;
- cout << endl;
- cout << "创建一个节点为" << n << "的单链表" << endl;
- p = createList(n);
- cout << endl;
- cout << "这步为程序逆置单链表" << endl;
- q = ReverseList(p);
- cout << endl;
- cout << "打印逆置后的单链表" << endl;
- print(q);
- cout << endl;
- return 0;
- }
方法二:用p,q指向单链表中相邻的两节点,将r指向q的下一个结点,然后同步后移。当q=NULL时,表示指向原单链表的尾结点,将p赋值为头节点 head 即可。
逆置函数代码如下(其他部分不变):
List *ReverseList(List *head)
{
List *p, *q, *r;
p = head;
if (p->next == NULL)
return head;
q = p->next;
while (q != NULL) //q为空,说明p为最后一个节点,所以结束while后将q赋值给head,作为逆置后的表头
{
r = q->next;
q->next = p;
p = q;
q = r;
}
head->next = NULL; //将原head变为逆置后链表的表尾
head = p; //逆置后新的表头
return head;
}