问题描述

设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值

算法思想

如果此题是不带头结点的单链表时，使用递归是最简单的方式。但是因为拥有头结点，因此如果继续使用递归会将头节点输出，而头结点本身并不存储任何数据，因此递归必然出错。
本题中，首先将头（head）结点单独摘下，形成头结点和后继链表两个部分；采用2.1.1头插法建立单链表中头插法的思想，因为采用头插法建立的单链表与输入数据时的顺序恰好是相反的，这样以来，我们便可以从后继链表中取出一个链头结点采用头插法插入到head结点之后；以此类推，便可以完成整张链表的反转操作，最后输出便可。

算法描述

LinkList Reverse(LNode *head){
    LNode *p=head->next;
    LNode *q=p;

    head->next=NULL;
    while(p){
        q=q->next;
        //单独拆出结点p
        p->next=NULL;
        //头插法在头结点后插入结点p
        p->next=head->next;
        head->next=p;
        //指针p重新指向原来被拆断的链的链头
        p=q;
    }
    return head;
}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

LinkList CreatList(LNode*);
LinkList Reverse(LNode*);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head->next=NULL;
    head=CreatList(head);
    Print(head);

    head=Reverse(head);
    Print(head);

    return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode *head)
{
    LNode *s,*r=head;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return head;
}
//反转结点
LinkList Reverse(LNode *head){
    LNode *p=head->next;
    LNode *q=p;

    head->next=NULL;
    while(p){
        q=q->next;
        p->next=NULL;
        p->next=head->next;
        head->next=p;
        p=q;
    }
    return head;
}
//打印所有结点
void Print(LNode *head){
    LNode *p=head->next;
    while(p){
        printf("%4d",p->data);
        p=p->next;
    }
    printf("
");
}