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

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

// 尾插法
void list_tail_insert(LinkList &L){
    L = (LinkList) malloc(sizeof (LNode));
    L->next = NULL;
    ElemType x;
    scanf("%d", &x);
    LNode *s, *r=L;
    while (x != 9999){
        s = (LinkList) malloc(sizeof (LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
}

// 打印链表
void print_list(LinkList L){
    L = L->next;
    while (L != NULL){
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

// 找到链表中间结点，并设置好L2链表
void find_middle(LinkList L, LinkList &L2){
    L2 = (LinkList) malloc(sizeof(LNode));
    LinkList pcur, ppre;  // 双指针法
    pcur = ppre = L->next;
    while (pcur){
        pcur = pcur->next;
        if(NULL == pcur){   // 为了防止pcur为NULL
            break;
        }
        pcur = pcur->next;
        if(NULL == pcur){   // 为了使偶数个结点时，ppre依然指向中间结点，a1~a6中的a3，如果不加判断，会指向a4
            break;
        }
        ppre = ppre->next;
    }
    L2->next = ppre->next; // L2头结点指向后面一半链表
    ppre->next = NULL;  // 前一半链表的最后一个结点的next为NULL
}

// 逆转链表
void reverse(LinkList L2){
    LinkList r, s, t;
    r = L2->next;
    if(NULL == r){
        return;  // 链表为空
    }
    s = r->next;
    if(NULL == s){
        return;  // 链表只有一个结点
    }
    t = s->next;
    while (t){
        s->next = r;  // 原地逆置
        r = s;   // 以下3句是3个指针同时向后移一步
        s = t;
        t = t->next;
    }
    s->next = r;
    L2->next->next = NULL;  // 原来的链表的第一个结点的指针域要指向NULL
    L2->next = s;   // 新的链表的头结点要指向s
}

// 合并两个链表
void merge(LinkList L, LinkList L2){
    LinkList pcur, p, q;
    pcur = L->next;   // pcur始终指向组合链表的链表尾
    p = pcur->next;   // p用来遍历L1链表
    q = L2->next;    // q指向L2第一个结点，q用来遍历L2链表
    while (p!=NULL && q!=NULL){
        pcur->next = q;
        q = q->next;
        pcur = pcur->next;
        pcur->next = p;
        p = p->next;
        pcur = pcur->next;
    }
    // 任何一个链表都可能剩余一个结点，需要再添加到链表中
    if(p!=NULL){
        pcur->next = p;
    }
    if(q != NULL){
        pcur->next = q;
    }
}

int main(){
    LinkList L;
    list_tail_insert(L);
    print_list(L);
    printf("---------------------\n");
    // 寻找中间结点
    LinkList L2 = NULL;
    find_middle(L, L2);
    print_list(L);
    print_list(L2);
    printf("---------------------\n");
    // 逆转链表L2
    reverse(L2);
    print_list(L2);
    printf("---------------------\n");
    // 合并L和L2
    merge(L, L2);
    free(L2);
    print_list(L);
    return 0;
}

单链表结点个数为奇数

单链表结点个数为偶数

时间复杂度分析

• 找到链表中间结点的函数find_middle的while循环遍历次数为n/2，因此该算法的时间复杂度为O(n)；
• 逆置链表的函数reserve只逆置了L2链表，while循环遍历次数为n/2，该算法时间复杂度为O(n)；
• 合并链表函数merge的while循环遍历次数为n/2，该算法时间复杂度为O(n)；
• 综上，上面3个函数总的运行次数是1.5n，忽略首项系数，因此算法总体时间复杂度为O(n)。