【数据结构】单链表就地逆置算法C语言

淡淡的烟草味﹌ 2023-03-03 11:15 84阅读 0赞

### 单链表就地逆置算法 ###

*   *   *  程序样例

在C语言中为了减少时间和空间，对单链表采用就地逆置的方法，话不多说，完整代码如下。

#include<stdio.h>
    #include<malloc.h>
    #define LEN sizeof (struct Node)
    struct Node
    {
        
    	int data;//定义数据域
    	struct Node *next;//定义指针域
    	 int length;//记录顺序表的长度
    };
    
    //建立动态链表
    struct Node *crt_list()                        
    {
        
    	struct Node *h, *p,*q;
    	int n;
    	h=(struct Node *)(malloc(LEN));
    	q=h;
    	printf("请输入一串整型数据（-1结束输入）：\n");
    	scanf("%d",&n);//输入数据
    	while(n!=-1)
    	{
        
    		p=(struct Node*)(malloc(LEN));
    		p->data=n;
    		q->next=p;//联接头节点
    		q=p;//指针移动
    		scanf("%d",&n);//再次输入数据
    	}
    	q->next=NULL;//条件为假，退出循环，将最后一个节点标志为尾结点
    	return h;
    }
    
    //输出链表
    void prt_list(struct Node *h)                    
    {
        
    	struct Node *p;
    	p=h->next;//指向第一个节点
    	if(p==NULL)
    			printf("Linked list is null\n");
    	else 
    			while(p!= NULL)
    			{
        
    				printf("%d",p->data);//输出数据
    				p=p->next;//指针移动
    			}
    }
    
    //就地逆置
    void NiZhi_list(struct Node *h)						
    {
        
    	struct Node *p,*q,*x;
    	p=h->next;
    	h->next=NULL;
    	while(p!=NULL)
    	{
        
    		q=p;
    		p=p->next;
    		q->next=h->next;
    		h->next=q;
    	}
    	x=h->next;
    	if(x==NULL)
    		printf("链表为空");
    	else
    		while(x!=NULL)
    		{
        
    			printf("%d",x->data);
    			x=x->next;
    		}
        
    }
    void main()
    {
        
    	struct Node *head; //定义一个结构体头指针
    	head=crt_list();//head指向建立的链表
    	printf("当前链表为： \n");
    	prt_list(head);                  
    	printf("\n");
    	printf("就地逆置后的链表为: \n");
    	NiZhi_list(head);
    	printf("\n");
    }

### 程序样例 ###

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

[20200731085600874.png]: /images/20230208/1d4bff2625e74295a08612468086aa52.png