单链表-C语言

线性表L=(a~1~，a~2~，a~3~，...，a~n-2~，a~n-1~，a~n~)采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node{
    int data;
    struct node* next;
}NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L^1^=(a~1~，a~n~，a~2~，a~n-1~，a~3~，a~n-2~，...)。要求：

1、给出算法的基本设计思想

2、根据设计思想，采用C或C++语言描述算法，关键之处给出注释

3、说明你所设计的算法的时间复杂度

解读：

首先空间复杂度O(1)，代表不能申请额外的空间，然后找到链表的中间结点，前面一半是链表L，将链表的后半部分分给一个带头结点的单链表L2，然后将链表L2原地逆置，然后再将L和L2链表进行合并。

解题思路：

第一阶段，如何找到链表的中间结点

两指针同步向后遍历法，定义两个指针pcur，ppre，让pcur指针每次走两步，ppre指针每次走一步，这样当pcur指针走到最后，那么ppre指针刚好在中间。这样方法无论链表结点总数目是奇数个还是偶数个，都能够顺利找到相对的中间结点。注意：pcur指针每次循环走两步，因此每次走一步都需要判断是否为NULL。

第二阶段，L2链表原地逆置

初始阶段需要判断链表是否为空，为空就直接返回结果，如果链表只有一个结点，不需要逆置，直接返回结果。检查完成后，开始逆置。

1、定义三个指针，分别为r、s、t，它们分别指向1、2、3，即链表的前三个结点。

2、让s->next=r，这样2号结点就指向了1号结点，完成了逆置。

3、令r=s、s=t、t=t->next，通过这个操作，r、s、t指针就分别指向了链表的2、3、4结点。

4、循环2、3步骤，当t=NULL时，结束循环。

5、循环结束时，t=NULL，此时s为最后一个节点，r为倒数第二个节点，需要再执行s->next=r，让最后两个结点逆置。

6、最后需要执行L2->next->next=NULL，因为原有链表的头结点变成链表的最后一个节点，最后一个节点的next指针需要指向NULL，此时执行L2->next=s，让L2指向s，因为s原本是链表的最后一个结点，逆置后，变成了第一个结点，所以链表头结点指向s。

第三阶段，L和L2链表合并，合并时轮流放入一个结点

因为空间复杂度是O(1)，所以不会申请新的空间。

1、定义三个指针，分别为pcur、p、q，pcur指针始终指向合并后的新链表的尾部，pcur指针初始化状态为pcur=L->next。p指针始终指向链表L待放入的结点，初始化状态为p=L->next。q指针始终指向链表L2待放入的结点，初始化状态为q=L2->next。因为链表L的第一个结点不动，所以p=p->next。

2、开启循环while(p!=NULL && q!=NULL)，执行pcur->next=q，将L2的第一个结点插入到L链表的第一个节点后，然后执行q=q->next和pcur=pcur->next，将q指针和pcur指针都后移一位。

3、随后执行pcur->next=p，将L的第二个节点插入到新的L链表当中，然后执行p=p->next和pcur=pcur->next，将p指针和pcur指针都后移一位，直到循环结束。

4、循环结束后，有可能链表L还剩余一个结点，也可能链表L2剩余一个节点，但是仅且只有一个链表会有剩余。因此判断p、q任意不为NULL，则把剩余结点放入新链表L。

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

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next; //指向下一个结点
}LNode,*LinkList;

//尾插法新建链表
LinkList list_tail_insert(LinkList &L){
    int x;
    L=(LinkList) malloc(sizeof(LNode));
    LNode *s,*r=L; //r代表链表表尾节点，指向链表尾部
    //LinkList s,r=L; //与上面语句等价
    scanf("%d",&x);
    while (x!=9999)
    {
        s=(LNode*) malloc(sizeof(LNode));
        s->data=x;
        r->next=s; //尾部结点指向新结点
        r=s; //r指针指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NULL; //尾结点的next指针赋值给NULL
    return L;
}

//打印链表
void PrintList(LinkList L){
    L=L->next;
    while(L!=NULL) //判断是否为最后一个结点，或链表为空
    {
        printf("%3d",L->data); //打印当前结点数据
        L=L->next; //指向下一个结点
    }
    printf("\n");
}

//查找中间结点
void find_middle(LinkList L,LinkList &L2){
    L2=(LNode*) malloc(sizeof(LNode));
    LinkList pcur,ppre;
    pcur=ppre=L->next;
    while (pcur!=NULL)
    {
        pcur=pcur->next; //先步进一步
        if(pcur==NULL) //判断是否已经到达尾部
        {
            break; //跳出循环
        }
        pcur=pcur->next; //大哥走两步
        if(pcur==NULL)
        {
            break;
        }
        ppre=ppre->next; //小弟只走一步
    }
    L2->next=ppre->next; //L2成为链表的后一半
    ppre->next=NULL; //L成为链表的前一半
}

//原地逆置链表
void reverse(LinkList L2){
    LinkList r,s,t;
    r=s=t=L2->next;
    if(r==NULL) //链表为空
    {
        return;
    }
    s=t=t->next;
    if(t==NULL) //链表只有一个结点
    {
        return;
    }
    t=t->next;
    while (t!=NULL)
    {
        s->next=r;
        r=s;
        s=t;
        t=t->next;
    }
    s->next=r;
    L2->next->next=NULL; //原本L2头结点指针指向的结点已经变成了尾结点，尾结点需要指向NULL
    L2->next=s; //将L2头结点指针指向s，s为新的链表头部
}

//两个链表交叉合并
void merge(LinkList L,LinkList L2){
    LinkList pcur,p,q;
    pcur=p=L->next;
    q=L2->next;
    p=p->next;
    while (p!=NULL && q!=NULL)
    {
        pcur->next=q; //链表L2给过来一个结点
        q=q->next; //给过元素就往后走一步
        pcur=pcur->next; //新链表表尾指针往后走一步
        pcur->next=p; //链表L给过来一个结点
        p=p->next; //给过元素就往后走一步
        pcur=pcur->next; //新链表表尾指针往后走一步
    }
    if(q!=NULL)
    {
        pcur->next=q;
    }
    if(p!=NULL)
    {
        pcur->next=p;
    }
}
int main(){
    LinkList L; //链表头，是结构体指针类型
    LinkList search; //用来存储拿到的某一结点
    list_tail_insert(L); //输出数据可以为 3 4 5 6 7 9999
    PrintList(L); //打印链表
    //寻找中间结点，并返回第二条链表
    LinkList L2;
    find_middle(L,L2);
    printf("--------------------------------\n");
    PrintList(L);
    PrintList(L2);
    printf("--------------------------------\n");
    reverse(L2);
    PrintList(L2);
    printf("--------------------------------\n");
    merge(L,L2);
    free(L2);
    PrintList(L);
    return 0;
};

时间复杂度

让我们逐个分析每个子函数的时间复杂度：

1. list_tail_insert（）: 这个函数的时间复杂度取决于输入的元素数量。在每次循环中，我们分配了一个新的结点并将其链接到链表的末尾。假设有 ( n ) 个元素，则时间复杂度为 ( O(n) )，其中 ( n ) 是元素的数量。

2. PrintList（）: 这个函数只是简单地遍历整个链表并打印每个元素。因为它只遍历一次链表，时间复杂度是 ( O(n) )，其中 ( n ) 是链表中的元素数量。

3. find_middle（）: 在这个函数中，我们使用了一种双指针技巧来找到链表的中间结点。由于我们只遍历了链表一次，因此时间复杂度是 ( O(n) )，其中 ( n ) 是链表中的元素数量。

4. reverse（）: 这个函数用于将链表原地逆转。它遍历了整个链表一次，并且对于每个结点，只有常数次操作。因此，时间复杂度是 ( O(n) )，其中 ( n ) 是链表中的元素数量。

5. merge（）: 这个函数用于合并两个链表。在这个函数中，我们遍历了两个链表中的元素，并且对于每个元素只有常数次操作。因此，时间复杂度也是 ( O(n) )，其中 ( n ) 是两个链表中的元素数量之和。

因此，最终算法的时间复杂度主要由 list_tail_insert（）、find_middle（）、reverse（） 和 merge`（）函数的时间复杂度决定，它们都是 ( O(n) )。因此，最终算法的时间复杂度是 ( O(n) )，其中 ( n ) 是输入链表中的元素数量。