将一个链表按逆序排列，将链头当链尾，链尾当链头。（头插法实现链表的逆置）

小鱼儿 2022-03-26 10:58 216阅读 0赞

**一、逆置算法如下：**

/*头插法实现单链表的逆置*/ 
    LNode* InvertLinklist(LNode *L)
    {
    	LNode *New=NULL,*p=L,*temp;     //New为新链表的头指针，temp为辅助指针 
    	while(p)                        //若首结点不为空则循环 
    	{ 
    		temp=p->next;               //将第二个结点赋给temp
    		
    		 
    /*......这部分与头插法一样......*/ 
    		p->next=New;                //将第一个结点的后继指针指向为空 
    		New=p;                      //头指针指向第一个结点 
    /*..............................*/
    
    		p=temp;	                    //将第二个结点赋给P实现下次循环 
    	}
    	return New;
    }

**二、实例代码如下:**

#include<stdio.h>
    #include<stdlib.h> 
    
    #define   LEN   10
    typedef  int  Elemtype;
    typedef struct LNode{
    	Elemtype  data;
    	struct LNode *next;
    }LNode;
    
    /*尾插法构建无头结点单链表*/
    LNode* CreateLinklist(LNode *L)
    {
    	LNode *p,*q;
    	L=NULL;
    	p=L;
    	for(int i=0;i<LEN;i++)
    	{
    		q=(LNode*)malloc(sizeof(Elemtype));
    		scanf("%d",&q->data);
    		if(p==NULL)
    		{
    			L=q;
    		}
    		else
    		{
    			p->next=q;
    		}
    		p=q;	
    	}
    	p->next=NULL;
    	return L; 
    }
    
    /*头插法实现单链表的逆置*/ 
    LNode* InvertLinklist(LNode *L)
    {
    	LNode *New=NULL,*p=L,*temp;     //New为新链表的头指针，temp为辅助指针 
    	while(p)                        //若首结点不为空则循环 
    	{ 
    		temp=p->next;               //将第二个结点赋给temp
    		
    		 
    /*......这部分与头插法一样......*/ 
    		p->next=New;                //将第一个结点的后继指针指向为空 
    		New=p;                      //头指针指向第一个结点 
    /*..............................*/
    
    		p=temp;	                    //将第二个结点赋给P实现下次循环 
    	}
    	return New;
    }
    
    /*单链表输出函数*/ 
    void PrintLinklist(LNode *L)
    {
    	LNode *p=L;
    	while(p)
    	{
    		printf("%d-->",p->data);
    		p=p->next;
    	}
    	printf("NULL\n");
    }
    
    int main()
    {
    	LNode *head,*L,*New;
    	head=CreateLinklist(L);         //创建单链表 
    	PrintLinklist(head);            //输出逆置前的单链表 
    	New=InvertLinklist(head);       //调用逆置函数 
    	PrintLinklist(New);            //输出逆置后的单链表 
    	return 0;	
    }

**三、运行效果截图：**

![在这里插入图片描述][20190116234143717.png]

[20190116234143717.png]: /images/20220326/5bb3e2ce72e141b482116a6bb45498bb.png