YTU 2991: 連結清單節點逆置（線性表）

2991: 連結清單節點逆置（線性表）

時間限制: 1 Sec  

記憶體限制: 128 MB

送出: 14  

解決: 6

題目描述

設計一個算法，将一個帶頭節點的資料域依次為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      

提示

​​1、請使用C++編譯并送出​​

​​2、隻需送出Deal算法​​

迷失在幽谷中的鳥兒，獨自飛翔在這偌大的天地間，卻不知自己該飛往何方……

#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;
}