https://blog.csdn.net/CSDNGuoYuying/article/details/86532357
自上篇文章写完单链表的建立（有头结点）的两种建立方法后，今天再写一下尾插法无头节点的建立方法及两种链表逆置方法（头插法与就地逆置）
1.尾插法建立链表

node *createTail(void)
{
	int m;
	node *current=NULL,*head=NULL,*tail=NULL;
	while(scanf("%d",&m)==1)
	{
		current=(node*)malloc(sizeof(node));
		if(head==NULL)
			head=current;
		else
			tail->next=current;
		current->a=m;
		tail=current;
	}
	tail->next=NULL;
	return head;
}

2.输出函数

void printfLink(node *head)
{
	node *p=head;
	while(p!=NULL)
	{
		printf("%d  ",p->a);
		p=p->next;
	}
	printf("\n");
}

尾插法输出效果

23 56 89 65 21 .
23  56  89  65  21
Press any key to continue

有无头结点区别在于头结点上，所以代码也是差不多，只是在有头结点的基础上加入了一个head结点判断。

链表逆置

头插法

接上篇写完头插法建立链表的方法后，小伙伴们对头插法的思路应该有一个较为明确的思路，头插法建立链表的思路很简单，就是创建一个新节点，再将新节点始终插入到头结点的后面，最后填补数据域。
由于头插法得到的数据本身就是逆置的，所以我们可以用头插法对已有的链表进行逆置操作。
用头插法对链表进行逆置和用头插法建立新链表的思路如出一辙，只不过是节点和数据已经给我们了，让我们在原有链表的基础上执行拆节点----头插这一循环操作。

大体思路我们了解了，就是拆节点----头插，可是具体该怎么实现，如何拆节点，怎么拆才能保证依旧可以寻址到后面的链表，显然头插很容易，那主要思考的部分就是拆节点了。

如果把头插逆置的整个过程比作一个加工厂，厂里有两个机器猫A和B和一堆散乱存放的产品，每一个产品上标有序号，但产品在货架上是散乱存放的，而其中每一个产品上都标有下一个产品的货架位置。它们要完成将产品按照与原来顺序相反的顺序存放的任务。
机器猫A和B用以下的方式通力合作完成了任务。
其中机器猫A顺着产品链一直往后走，每到一个产品前停顿一下，等待着将面前的产品传递给机器猫B，机器猫B找到机器猫A的位置，拿到机器猫A面前的产品，（此时机器猫A记下刚才被拿走的产品上面的地址，继续往后走到下一个产品前等待机器猫B，）并且每次将产品送到第一个产品的前面，然后去找到机器猫A的位置继续重复以上工作。

头插法逆置与上述思路一致，首先我们需要两只机器猫。
即定义一个指针变量pLink寻找节点并且交接节点；
再定义一个指针变量pPrev将交接的节点放到第一个节点之前；
由于还需要一个头结点辅助头插，所以在这里我们也建立一个指针变量pHead

	node *pHead,*pPrev=NULL,*pLink=NULL;

	pHead=(node*)malloc(sizeof(node));
	pHead->next=NULL;//创建辅助头插的头节点

准备工作：先让pLink找到第一个节点

	pLink=head;//   head为待逆置链表的第一个节点

循环拆节点----头插

	while(pLink)
	{
		pPrev=pLink;//  交接节点
		
		pLink=pLink->next;//  pLink找到下一节点

		pPrev->next=pHead->next;
		pHead->next=pPrev;//  pPrev将交接到的节点放到第一个节点之前（辅助头结点之后）
	
	}

去掉辅助头结点

	pHead=pHead->next;//去掉辅助头插的节点

头插法逆置完整代码

node *reverseList(node *head)
{
	node *pHead,*pPrev=NULL,*pLink=NULL;

	pHead=(node*)malloc(sizeof(node));
	pHead->next=NULL;//创建辅助头插的新节点

	pLink=head;

	while(pLink)
	{
		pPrev=pLink;//赋值
		
		pLink=pLink->next;//移动到下一节点

		pPrev->next=pHead->next;
		pHead->next=pPrev;//链接
	
	}
	pHead=pHead->next;//去掉辅助头插的节点

	return pHead;

}

就地逆置

如果不用头插法如何将链表逆置？
其实思路与头插逆置大体上相同，只是就地逆置不用头插法，故而用不到辅助头结点。
如果没有辅助头结点如何照猫画虎将上述思路搬下来呢？
显然思路一样，需要一个指针变量pLink寻找节点并且交接节点，也需要指针变量pPrev将交接到的节点放置在每次更新链表后第一个节点的前面。
循环进行此操作，就完成了逆置。
既然没有辅助头结点，显然我们的插入操作一步就可以完成
pPrev->next=第一个节点;
但是由于第一个节点每次都会更新，所以我们还需要一个指针变量p来更新链表的第一个节点。

完整代码如下

node *landReverseList(node *head)
{
	node *pLink=head,*pPrev=NULL,*p=NULL;
	while(pLink)
	{
		pPrev=pLink;//交接

		pLink=pLink->next;//pLink找到下一节点

		pPrev->next=p;//链接交接节点与p节点
		p=pPrev;//移动p节点，使p节点始终指向第一个节点

	}
	return p;
}

看完后希望能对你有帮助鸭~~~