第1章第2节练习题15 拆分并逆序单链表

问题描述

设 C={a1,b1,a2,b2,...,an,bn} 为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A={a1,a2,a3,...an} ， B={bn,...,b2,b1} 。

算法思想

本题实际上跟 第1章第2节练习题8 奇偶拆分单链表 大同小异。
因为本题中原来的单链表基本递增有序，因此采用尾插法创建单链表可以避免创建的链表与逻辑顺序相反的问题，然后将序号为偶数的结点摘下，然后通过头插法创建单链表的方式星驰单链表B，这样以来便就形成了正序的序列A和逆序的序列B。

算法描述

LinkList SeparateList(LNode* head){
    LNode *hb;
    hb=(LNode*)malloc(sizeof(LNode));
    LNode *pre=head;
    LNode *p=head->next;

while(p){
if(p->num%2==0){
            pre->next=p->next;
            p->next=hb->next;
            hb->next=p;
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
return hb;
}

具体代码见附件。

---

附件

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

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

LinkList CreatList(LNode*);
LinkList SeparateList(LNode*);
int LengthList(LNode*);
void Print(LNode*);

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

    LNode *ha;
    LNode *hb;
    hb=SeparateList(hc);
    ha=hc;
    Print(ha);
    Print(hb);
}
//尾插法建立单链表
LinkList CreatList(LNode* head)
{
    LNode *r=head;
    LNode *L;
    ElemType x;
int i=1;
scanf("%d",&x);
while(x!=999){
        L=(LNode*)malloc(sizeof(LNode));
        L->num=i++;
        L->data=x;
        r->next=L;
        r=L;
scanf("%d",&x);
    }
    r->next=NULL;
return  head;
}
//分离单链表
LinkList SeparateList(LNode* head)
{
    LNode *hb;
    hb=(LNode*)malloc(sizeof(LNode));
    LNode *pre=head;
    LNode *p=head->next;

while(p){
if(p->num%2==0){
            pre->next=p->next;
            p->next=hb->next;
            hb->next=p;
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
return hb;
}
//打印全部结点
void Print(LNode* head)
{
    LNode *p=head->next;
while(p){
printf("%4d",p->data);
        p=p->next;
    }
printf("\n");
}