数据结构【2019年408第41题】

（1）一个N长度的链表的为了按照题目的需求，我们观察可以发现可以将一个链表从中间分开然后逆置然后依次插入则我们大致的思路如下：

1.将链表分为两段，L和L2

2.将L2逆置从顺的顺序变为反过来的顺序

3.将L和L2按照 L -> L2 -> L -> L2 ...这样的顺序连接

这时候L的链表可以完成体重所给的需求

（2）代码如下：

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

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

//尾插法输入链表
void ListTailInsert(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LinkList s ,r=L;
    ElemType elem;
    scanf("%d", &elem);
    while(elem != 9999){                        //输入数值为9999时中断循环，链表建立成功
        s = (LinkList)malloc(sizeof(LNode));
        s->data = elem;
        s->next = NULL;
        r->next = s;
        r = s;
        scanf("%d", &elem);
    }
}

//输出链表（中断输出条件是为最后的结点指向NULL）
void PrintList(LinkList L){
    L=L->next;
    while(L){
        printf("%-3d", L->data);
        L=L->next;
    }
    printf("
");
}

//将链表分为前后两段
void PiecewiseFunction(LinkList L,LinkList &L2){
    L2 = (LinkList)malloc(sizeof(LNode));
    L2->next = NULL;
    LinkList pc,pp;         //双指针遍历法
    pc = L->next;
    pp = L->next;
    while(pc){
        if(pc->next != NULL){
            pc =  pc->next;         //pc指针下一步不为空时，前进一步
            if(pc->next != NULL){
                pc =  pc->next;     //pc指针再下一步不为空时，再前进一步
                pp = pp->next;      //此时pc前进两部，pp前进一步
            }
        } else{
            break;          //只要pc的下一步为空则退出循环
        }
    }
    L2->next = pp->next;    //此时pp在这个两表中心位置，将中心后面的指针发给L2，让他成为新的头节点指针指向后一段的链表
    pp->next = NULL;        //将前一个链表的最后一个位置指向NULL
}

//将L2链表进行反置
void InversionFunction(LinkList L2){
    LinkList r,s,t;
    r = L2->next;
    if(r == NULL){              //L2中没有数值不需要反转
        return;
    }
    s = L2->next->next;
    if(s == NULL){              //L2中只有一个数值不需要反转
        return;
    }
    t = L2->next->next->next;
    if(t == NULL){              //L2中只有两个数值则只需要反转一次
        s->next = r;
        r->next = NULL;
        L2->next = s;
        return;
    }
    r->next = NULL;
    while (t != NULL){          //L2中有大于两个数值则则需要多次反转
        s->next = r;
        r = s;
        s = t;
        t = t->next;
    }
    s->next = r;
    L2->next = s;               //此时的链表头部在s的位置，将s交给L2
}

//合并两个链表，通过三个指针将两个链表进行来回的连接上
void MergeFunction(LinkList L,LinkList L2){
    LinkList pc,p,q;
    pc = L->next;
    p = L->next;
    q = L2->next;
    while(p != NULL && q != NULL){ //因为在分段函数的时候将长的一段交给L所以此时只要L2为空或者L为空，那么就肯定连接完成，不需要再判断
        p = p->next;
        pc->next = q;
        pc = q;
        q = q->next;
        pc->next = p;
        pc = p;
    }
}

int main() {
    LinkList L;
    ListTailInsert(L);          //尾插法建立链表
    LinkList L2;                //建立第二个链表的头节点
    PiecewiseFunction(L,L2);    //将第一个链表从中间分段给L2
    InversionFunction(L2);      //将L2链表反置
    MergeFunction(L,L2);        //将L于L2按照 L -> L2 -> L -> L2 ...这样的顺序连接
    free(L2);                   //释放L2的空间
    PrintList(L);               //打印链表
    return 0;
}

（3）每一段函数的运行次数都是0.5n 总共为1.5n次，则时间复杂度都为O(n)，忽略首项系数了。