编写函数实现链表的逆置的算法分析

head指向一个单向链表，链表中每个结点包含数据域（）和指针域（）。请编写函数实现链表的逆置。

实现代码如下：

/* 编写函数实现链表的逆置。*/
#include /*标准输入、输出函数库*/
#include
#define LEN sizeof(struct list)

/*定义节点数据类型*/
struct list{
int data; /*节点的数据类型，可以是其它类型*/
struct list * next;
};

/* 创建链表，并返回表头指针 */
struct list * create(void);

/*对链表逆置的函数*/
struct list * invert(struct list *);

/*输出链表*/
void print(struct list *);

int main()
{
struct list *h,*t; /*定义一个链表，h为头指针*/
h = create(); /*创建链表*/
printf("创建的链表是：\n");
print(h); /*输出所创建的链表*/
t=invert(h); /*对链表进行逆置*/
printf("逆置后的链表是：\n");
print(t); /*输出逆置后的链表*/

return 0;
}

struct list * create() /* 创建链表，并返回表头指针。带一个头指针的链表 */
{
struct list *head; /* 表头 */
struct list *p; /* 新建结点 */
struct list *tail; /*表尾节点*/
int input; /*输入的数据*/

head = NULL; /* 还没有任何数据，表头为空 */
tail = head; /*尾指针首先指向表头指针*/
printf("请输入结点数据：\n");
scanf("%d",&input);
while (input!=0) /* 假设data为0表示输入结束 */
{
p = (struct list *)malloc(LEN); /* 新建一个结点 */
p->data=input;
p->next=NULL;
if (head==NULL)/*链表为空表*/
head=p;
else
tail->next = p; /* 在表尾链接新结点 */
tail = p; /* 新建结点成为表尾 */
printf("请输入结点数据：\n");
scanf("%d",&input);
}

if (head!=NULL) /*输入了数据，已插入节点*/
tail->next = NULL; /* 输入结束，表尾结点的下一个结点为空 */
return head; /* 返回表头指针 */
}

void print(struct list *head) /*输出链表*/
{

if (head==NULL)
{
printf("链表空！\n");
return;
}
while(head != NULL)
{
printf("%4d",head->data);
head = head->next;
}
printf("\n");
}

/*对链表逆置的函数*/
struct list * invert(struct list * head)
{
    struct list *p,*q; /*用于逆置的中间变量*/
    if (head==NULL)
   {
       printf("链表空！\n");
       return head;
    }
    p=head;
    head=NULL;
    while (p!=NULL)
    {
         q=p->next;
         p->next=head;
         head=p;
         p=q;
     }
    return head;
}

采用双指针的单链表逆置的代码示例如下：

typedef struct node
{
 int data;
 node *next;
}node;

void fun(node **head)
{
 node *p1, *p2, *p3;
 p1 = *head;
 
 p2 = p1->next;
 p3 = p2->next;
 p1->next = NULL;
 while(p3!= NULL)
 {
  p2->next = p1;
  p1 = p2;
  p2 = p3;
  p3 = p3->next;
 }
 p2->next = p1;
 *head = p2;
} 

int main(int argc, char* argv[])
{
 struct node *mylist,*head;
    struct node *templist;
    struct node *tempheaser;
 int i;
    mylist = (struct node *)malloc(sizeof(struct node));
 mylist->data=0;
 head = mylist;
    tempheaser = mylist;
 for(i = 0;i < 10; i++)
 {
  templist = (struct node *)malloc(sizeof(struct node));
  templist->data=i+1;
  tempheaser->next=templist;
  tempheaser = tempheaser->next;
 }
 tempheaser->next = NULL;
 
while(mylist != NULL)
 {
  printf("%d\n",mylist->data);
  mylist = mylist->next;
 }
 mylist = head;
 fun(&mylist);     ================= >>双指针传递变量
 while(mylist != NULL)
 {
  printf("%d\n",mylist->data);
  mylist = mylist->next;
 }

 return 0;
}