::: tip
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度，因为每次递归都要存储返回信息。
:::
解题设计：
::: tip
算法设计的三个阶段：
第一阶段中，当节点数为奇数如a1到a7七个节点时，中间节点ppre指向a4，当节点数为偶数如a1到a6六个节点时，中间节点ppre指向a3。中间节点为分界线，将链表分为L1、L2两个链表。一般为了方便节点数为奇数时将中间节点划分到第一个链表L1中。
（双指针同时遍历是链表操作的常用场景。）
第二阶段中，链表的逆置不影响L2头节点。
第三阶段中，两个链表合并的操作可以当作是将L2链表插入进L1链表中。和头插法区别是L2链表中的节点已经有空间了，不需要在申请空间。
:::
链表合并流程描述：组合后的新列表L以L1为基础，，L->next=L1->next即L指向的第一个节点为a1。pcur初始化指向第一个节点a1（此时L链表中只有一个节点a1，pcur指向新链表L的末尾节点即a1）。根据题意a1位置不变，p指向待放入节点的位置即L的a2，q指向L2的第一个节点，q指向的节点插入到L中的a2位置处时，pcur指向pcur的下一个节点a2（新链表尾部），q指向q的下一个节点。（新链表L中每添加一个节点，pcur都向后移动一个节点指向末尾）。
L独立出来如下图：
如上图a5是L1最后一个节点，p指向a5并放进L后，循环条件p!=NULL&&q!=NULL不成立，此时q指向a7，需要在循环外将q->next指向L2最后一个节点a6，然后pcur->next=q将a6放进L。
::: tip
链表逆置的时间复杂度是O(n)，链表合并的空间复杂度为O(1)。
:::
链表逆置
全部代码如下：
1#include <stdio.h> 2#include <stdlib.h> 3 4typedef struct node 5{ 6 int data; 7 struct node* next; 8}NODE; 9void insert_list(NODE*& L) 10{ 11 L = (NODE*)malloc(sizeof(NODE)); 12 L->next = NULL; 13 int x; 14 scanf("%d", &x); 15 NODE* s, * t; 16 t = L; 17 while (x != 9999) 18 { 19 s = (NODE*)malloc(sizeof(NODE)); 20 t->next = s; 21 s->data = x; 22 t = s; 23 scanf("%d", &x); 24 } 25 t->next = NULL; 26} 27void find_mid(NODE* L, NODE*& L2) //找到链表中间节点并设置好L2 28{ 29 L2 = (NODE*)malloc(sizeof(NODE)); //为L2申请头节点 30 NODE* pppre, * pcur; 31 pppre = pcur = L->next; //pppre指向中间节点，pcur指向最后一个节点 32 while (pcur) //循环到末尾时停止 33 { 34 pcur = pcur->next; 35 //不能连续走两步，每走一步后需要判断是否来到链表尾部 36 if (NULL == pcur) 37 { 38 break; 39 } 40 pcur = pcur->next; 41 if (NULL == pcur) //节点数为奇数时不需要这个判断，为偶数时需要，否则pppre会向下多走一步 42 { 43 break; 44 } 45 pppre = pppre->next; //pcur可以成功向下走，则pppre也可以，不需要再做判断 46 } 47 //pppre指向中间节点，属于L链表的最后一个节点，pppre以后的节点属于L2链表 48 L2->next = pppre->next; 49 pppre->next = NULL; 50} 51void reverse(NODE*& L2) 52{ 53 NODE* r, * s, * t; //r、s、t分别指向L2的前三个节点 54 r = L2->next; 55 if (NULL == r) //判断链表是否为空（没有节点） 56 { 57 return; 58 } 59 s = r->next; 60 if (NULL == s) //判断链表中是否只有一个节点 61 { 62 return; 63 } 64 t = s->next; 65 while (t) //t可以为空，t为空不影响其他指针 66 //while(t)等同于while(t!=NULL)，表示节点t不存在，即t的数据域和指针域都不存在 67 { 68 s->next = r; //节点逆置 69 //三个指针同时向后走一步 70 r = s; 71 s = t; 72 t = t->next; 73 //进入循环时已经确保节点t的存在，当t是最后一个节点t->next为NULL时，while循环跳出 74 } 75 s->next = r; 76 L2->next->next = NULL; //L2指向第一个节点，逆置后原来的第一个节点变为最后一个，指针域为空 77 L2->next = s; //此时链表的第一个节点变为s指向的节点，头节点的next指向链表第一个节点 78} 79 80void merge(NODE* L, NODE* L2) //L和L2的两个头节点不变，不需要引用& 81{ 82 NODE* pcur, * p, * q; 83 pcur = L->next; //pcur指向第一个节点 84 p = pcur->next; //p也可以指向pcur->next，即p从第二个节点开始加 85 q = L2->next; 86 while (q != NULL && p != NULL) //while (q && p) 87 { 88 //pcur始终指向L的末尾，每次向L中放入一个节点，pcur都要向后走一步 89 pcur->next = q; 90 q = q->next; //q用来遍历L2列表 91 pcur = pcur->next; 92 pcur->next = p; //p用来遍历L1列表 93 p = p->next; 94 pcur = pcur->next; 95 } 96 97 //两个链表中会有其一有剩余节点 98 if (p==NULL) 99 { 100 pcur->next = q; 101 } 102 if(q==NULL) 103 { 104 pcur->next = p; 105 } 106 //或如下： 107 //if (p != NULL) 108 //{ 109 // pcur->next = p; 110 //} 111 //if (q != NULL) 112 //{ 113 // pcur->next = q; 114 //} 115} 116 117void print(NODE* L) 118{ 119 L = L->next; 120 while (L != NULL) 121 { 122 printf("%3d", L->data); 123 L = L->next; 124 } 125 printf("\n"); 126} 127int main() 128{ 129 NODE* L; 130 insert_list(L); 131 print(L); 132 NODE* L2 = NULL; 133 find_mid(L, L2); //L2指向中间节点 134 reverse(L2); 135 print(L2); 136 merge(L, L2); 137 free(L2); 138 print(L); 139 return 0; 140}
所写代码的时间复杂度： 时间复杂度的分析重点是三个阶段写的三个子函数。 find_mid中的while循环条件是pcur!=NULL，pcur每次向后走两个节点，总的节点数为n时，while循环的次数是n/2，忽略首项系数1/2，时间复杂度为O(n)。 reverse中的while循环条件是t!=NULL，reverse逆置L2链表时对L2链表做遍历，L2链表中节点数为n/2，忽略首项系数1/2，时间复杂度为O(n)。 merge中的while循环条件是q!=NULL&&p!= NULL，p和q两条链表中节点数都为n/2，p和q遍历链表，循环遍历的次数为n/2，忽略首项系数1/2，时间复杂度为O(n)。 ::: warning 以上三个函数的总运行次数为n/2+n/2+n/2=1.5n，忽略首项系数1.5，整体时间复杂度为O(n)。 ::: ::: tip 时间复杂度不考虑代码的行数。 :::