关于单链表逆序的一个小问题

    以前只是在这里看，没有过自己动手写的打算，但是发现越来越多的小问题，记在各个地方还要麻烦的去找，所以还是也尝试着写一下博客，来记录一下自己嵌入式系统的学习之路，排版方面希望也能慢慢提高。

单链表逆序

  关于单链表逆序的问题。

关于单链表逆序。

最近学习到了单链表这块，基本的各种操作都能掌握，这里感觉最困难的是单链表逆序这一块（也打算尝试下写下双链表的逆序）。
听好多人说这个也是面试中常考的问题，所以对这方面着重的练习了一下。网上的方法也有好多，不过好多看起来都好复杂，每次都是研究到一半就想放弃，好不容易看明白了相应的各种方法。总结了各种方法，找出了我认为最简单的一种方法。

单链表逆序函数

代码如下

void reverse(pNode pHeader)
{
	pNode p = pHeader->pNext;
	pNode pn = NULL;
	pNode q = NULL;

	//把头指针和头结点断开
	pHeader->pNext = NULL;

	//这里我没有考虑只有头结点和头指针，一个有效节点也没有的情况。
	while (NULL != p)
	{
		pn = p->pNext;
		p->pNext = q;
		q = p;
		p = pn;
	}

	//把头结点和操作好的有序节点链接
	pHeader->pNext = q;
}

函数描述

这个是我个人感觉最简单的逆序算法了，思想就是先把头指针和头结点与后面要操作的有效节点分开。对于有效节点的操作方法是
例如：a-b-c-d-e个节点。
操作顺序是：
a
b-a
c-b-a
。。。
e-d-c-b-a
我先把a节点拿出来，记下a节点的首地址，以及给a->pNext一个辅助指针q。然后接着操作b节点，记下b节点的首地址，这时令b->pNext = a节点的首地址。完成 b-a。
所有的操作好了之后：
pHeader->pNext = q; 来把头结点和e节点的首地址链接，完成逆序。

运行结果

这里是含有，创建链表，遍历链表，链表逆序的代码。

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

//定义单链表
typedef struct Node
{
	int data;
	struct Node * pNext;
}Node, *pNode;


//调用函数
pNode static CreateLinked();
void traverse(struct Node * pHeader);
void reverse(pNode pHeader);

int main()
{
	pNode pHeader =  CreateLinked();

	reverse(pHeader);
	//Reverselist(pHeader);

	traverse(pHeader);

	return 0;
}

//生成一个单链表
pNode CreateLinked()
{
	int n, i, data;

	//先申请一个头指针和头结点
	pNode pHeader = (pNode)malloc(sizeof(Node));
	pHeader->data = 0;
	pHeader->pNext = NULL;
	
	printf("单链表有效节点数\n");
	scanf_s("%d", &n);

	pNode p = pHeader;
	for (i = 1; i <= n; i++)
	{
		pNode pNew = (pNode)malloc(sizeof(Node));    
		if (NULL == pNew)
		{
			printf("malloc erroe\n");
		}
		
		printf("输入节点%d的值\n", i);
		scanf_s("%d", &data);

		pNew->data = data;
	
		p->pNext = pNew;
		p = pNew;
		pNew->pNext = NULL;
	}

	pHeader->data = i-1;

	return pHeader;
}

//链表遍历
void traverse(struct Node * pHeader)
{
	int i = 1;
	struct Node * p = pHeader;

	printf("node总数 = %d\n", pHeader->data);

	while (NULL != p->pNext)
	{
		p = p->pNext;
		printf("node %d = %d\n", i, p->data);
		i++;
	}
}

//链表逆序
void reverse(pNode pHeader)
{
	pNode p = pHeader->pNext;
	pNode pn = NULL;
	pNode q = NULL;

	//把头指针和头结点断开
	pHeader->pNext = NULL;

	//这里我没有考虑只有头结点和头指针，一个有效节点也没有的情况。
	while (NULL != p)
	{
		pn = p->pNext;
		p->pNext = q;
		q = p;
		p = pn;
	}

	//把头结点和操作好的有序节点链接
	pHeader->pNext = q;
}

运行结果如下图

逆序中遇到的问题

其实我主要想记录的就是这个逆序中遇到的这个问题，一开始我的逆序函数中的代码如下

while (NULL != p)
	{
		p->pNext = q;
		q = p;
		p = p->pNext;
	}

修改后代码为

while (NULL != p)
	{
		pn = p->pNext;
		p->pNext = q;
		q = p;
		p = pn;
	}

也就是少了这个辅助指针pn。按照我自己的理解，上面那种情况应该能完成任务，结果怎么试也搞不出来，忙了一晚上，最后终于发现问题所在了，我定义的q = null。然后p->pNext = q;后，p后面已经没有节点了，所以后面的遍历完全不能进行了。
一定仔细细心，写代码时仔细一点能省好多时间

感觉第一次在这上面写，排版好乱啊，以后会慢慢加强这方面的，也希望对在学单链表逆序的人有帮助。