链表节点逆置(线性表)

链表节点逆置(线性表)

时间: 1ms        内存:128M

描述:

设计一个算法,将一个带头节点的数据域依次为a1,a2,…,an(n>=3)的单链表的所有节点逆置,即第一个节点的数据域变为an,……,最后一个节点的数据域变为a1,请尽量采用较优算法,时间复杂度为O(n)最佳!

线性表的定义为
typedef struct Node
{
    ElemType data;
    struct Node *next;
} SqList;
 
需编写的算法为
SqList *Deal(SqList *p);
 


注意:只需提交你所编写的算法

输入:

输入的第一行包含一个整数,代表单链表的长度。接下来的一行是链表每个节点的数据域的值。

输出:

输出包含一行,即逆置节点后链表的每个节点的数值。

示例输入:

10
1 2 3 4 5 6 7 8 9 10

示例输出:

10 9 8 7 6 5 4 3 2 1

提示:

参考答案(内存最优[0]):

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
int a[100];
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LinkList;
void IintList(LinkList *L)
{
    L=(LinkList *)malloc(sizeof(LinkList));
    L->next=NULL;
}
void CreatList(LinkList *L,ElemType a[],int n)
{
    LinkList *s,*r;
    int i;
    r=L;
    for(i=0; i<n; i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
void DispList(LinkList *L)
{
    LinkList *p=L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
void DestroyList(LinkList *L)
{
    LinkList *pre=L,*p=L->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=p->next;
    }
    free(pre);
}
int Reverse(LinkList *L)
{
    LinkList *p=L->next,*q=L->next;
    L->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    }
    return 1;
}
int main()
{
    LinkList L;
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
     scanf("%d",&a[i]);
    IintList(&L);
    CreatList(&L,a,n);
    if(Reverse(&L))
        DispList(&L);
    DestroyList(&L);
    return 0;
}

参考答案(时间最优[0]):


#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} SqList;
SqList *Init(int n)
{
    if(n<3)exit(-1);
    SqList *head=NULL,*p1,*p2;
    head=(SqList*)malloc(sizeof(SqList));
    p1=p2=(SqList*)malloc(sizeof(SqList));
    for(int i=0; i<n; i++)
    {
        if(i==0)head->next=p1;
        else p2->next=p1;
        scanf("%d",&p1->data);
        p2=p1;
        p1=(SqList*)malloc(sizeof(SqList));
    }
    p2->next=NULL;
    return head;
}
void Print(SqList *p)
{
    p=p->next;
    while(p->next!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d\n",p->data);
}SqList *Deal(SqList *p)
{
    SqList *a=p->next,*b=p->next->next,*c=p->next->next->next,*head=p;
    while(true)
    {
        if(a==p->next)a->next=NULL;
        b->next=a;
        if(c->next==NULL)
        {
            c->next=b;
            break;
        }
        a=b,b=c,c=c->next;
    }
    head->next=c;
    return head;
}
int main()
{
    int n;
    SqList *head=NULL;
    scanf("%d",&n);
    head=Init(n);
    head=Deal(head);
    Print(head);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注