就地逆置带头结点的单链表

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
/*2017年3月20日20:13:49就地逆置首先要了解“就地逆置”的含义：不再需要额外的空间来保存这个链表中的任何节点的数据域。而不是不需要任何空间。比如下面的例子就需要两个指针的空间。思路：①将原来的头结点拆下来，作为新的逆置链表的头结点②将原来链表的各个节点，依次拆卸下来，然后按照头插法，插入到逆置链表当中③循环，直到原来的链表为空即可。
*/typedef struct Node{int data;struct Node * next;
}Node;//定义节点类型void initList(Node * & List);
int addElement(Node * list,int x);
void printList(Node * list);
void ReverseList(Node * list);int main(void)
{Node * list;initList(list);for(int index=10;index>0;index--){addElement(list,index);//采用一个循环来给这个链表赋值1,2,3,4,5,6,7,8,9,10}printList(list);//打印出来的是1,2,3,4,5,6,7,8,9,10ReverseList(list);printList(list);//打印出来的是10,9,8,7,6,5,4,3,2,1system("pause");return 0;
}void initList(Node * & List)//初始化链表。//需要传引用型，因为需要list所指向的单元要改变。
{List=(Node*)malloc(sizeof(Node));memset(List,0,sizeof(Node));//注意，通过memset，可以直接对其进行初始化。return;
}int addElement(Node * list,int x)//头插法建立链表//不用传引用型的list，因为list始终指向的是头结点
{Node * now;now=(Node*)malloc(sizeof(Node));if(now!=NULL){now->data=x;now->next=list->next;list->next=now;return 1;}else{printf("申请空间失败！\n");return 0;}
}void printList(Node * list)//打印链表//不用传引用型的list，因为list始终指向的是头结点
{Node * p;p=list->next;while(p!=NULL){printf("%d\n",p->data);p=p->next;}
}void ReverseList(Node * list)//不用传引用型的list，因为list始终指向的是头结点
{Node *p,*q;p=list->next;list->next=NULL;while(p!=NULL){q=p->next;p->next=list->next;list->next=p;p=q;}//while           
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！