2019_41 考研408

2019年(单链表)

41.(13分)设线性表

采用带头结点的单链表保存，链表中的结点定义如下:

typedef struct node {

int data;

struct node* next;

}NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(q,a,,a,an-1,as,an-2y…)。要求:

(1)给出算法的基本设计思想。

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

(3)说明你所设计的算法的时间复杂度。

思路：因为题目要求要空间复杂度为O(1)，所以我们不能再额外申请空间了，然后再找到链表的中间结点，将其一分为二，分为L和L2的单链表，并将L2链表进行原地逆置，最后再将L和L2进行混合合并。

一、找到中间结点，并一分为二。

思路：定义两个指针p1和p2，p1指针每次走两步，p2指针每次走一步，当p1指针走到最后，p2指针必定走到中间结点。（写代码的过程中还应该注意总结点是奇数还是偶数）

代码段：

void find_middle(LinkList L,LinkList &L2)        //寻找链表中间结点，并设置好L2链表 
{L2 = (LinkList)malloc(sizeof(LNode));    //设置第二条链表的头结点 LinkList pcur,ppre;                        //双指针法，pcur跨两步，ppre跨一步。 ppre = pcur = L->next;    //一开始都指向第一个结点，即首元结点 while(pcur)        {pcur = pcur->next;if(pcur == NULL)    //防止pcur为空 {break;}pcur = pcur->next;    //若此处pcur为空，则不满足循环条件 if(pcur == NULL)    //为了使得偶数个，ppre依然指向a1，a2到a6中的a3结点 {break;}ppre = ppre->next;}L2->next = ppre->next;    //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre->next = NULL;     //此时的ppre为前一半链表的最后一个结点，最后一个结点的指针域应该为NULL     
}

二、将L2原地逆置

思路：分别定义3个指针r、s、t，让r、s、t分别指向前三个结点，再让第二个结点指向第一个结点，然后r、s、t同时向后移动一位，再让第三个结点指向第二个结点，然后r、s、t同时向后移动一位，如此往复循环，当t为null时循环结束。因为原有链表的头结点变成链表最后一个结点，最后一个结点应该指向NULL，最后让L2头结点指向新的首元结点s。

代码段：

void reverse(LinkList L2)    //逆转。因为L2的头结点不会发生改变 
{LinkList r,s,t;r = L2->next;    //一开始r指向首元结点 if(r == NULL){return ;//链表为空 }s = r->next;    //一开始r指向s if(s == NULL){return;//链表只有1个结点    } t = s->next;    //一开始让s指向twhile(t){s->next = r;    //原地逆置，让s指向r r = s;            //以下3句，是3个指针同时向后移动一位 s = t;t = t->next; } s->next = r;L2->next->next = NULL;//逆置后，原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2->next = s;    //此时s是逆置后链表的第一个结点，L2的头结点应该指向它 
}

三、将L与L2进行混合合并

思路：将L与L2链表合并，合并时分别轮流放入一个结点。定义3个指针pc、p、q，一开始指针pc指向L链表的首元结点，指针p指向L链表的第二结点，指针q指向L2链表的首元结点。并且让pc指针始终指向合并后新链表的尾部,使用p指针始终指向链表L待放入的结点，q指针始终指向链表L2待放入的结点。

代码段：

void merge(LinkList L,LinkList L2)    //将L与L2混合并合并 
{LinkList  pcur,p,q;pcur = L->next;    //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p = pcur->next;    //p指向L链表的第二个结点。p用来遍历L链表。 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;}
}

总代码：

#include<stdio.h> //2019年考研408真题，第41题 
#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;//用来指向申请的新结点LNode *r=L;//r始终指向链表尾部while(x != 999){s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;    //r->next指向s结点r = s;            //r要指向新的尾部 scanf("%d",&x); } r->next = NULL;    //让尾结点的next为NULL 
}void find_middle(LinkList L,LinkList &L2)        //寻找链表中间结点，并设置好L2链表 
{L2 = (LinkList)malloc(sizeof(LNode));    //设置第二条链表的头结点 LinkList pcur,ppre;                        //双指针法，pcur跨两步，ppre跨一步。 ppre = pcur = L->next;    //一开始都指向第一个结点，即首元结点 while(pcur)        {pcur = pcur->next;if(pcur == NULL)    //防止pcur为空 {break;}pcur = pcur->next;    //若此处pcur为空，则不满足循环条件 if(pcur == NULL)    //为了使得偶数个，ppre依然指向a1，a2到a6中的a3结点 {break;}ppre = ppre->next;}L2->next = ppre->next;    //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre->next = NULL;     //此时的ppre为前一半链表的最后一个结点，最后一个结点的指针域应该为NULL     
}                            void reverse(LinkList L2)    //逆转。因为L2的头结点不会发生改变 
{LinkList r,s,t;r = L2->next;    //一开始r指向首元结点 if(r == NULL){return ;//链表为空 }s = r->next;    //一开始r指向s if(s == NULL){return;//链表只有1个结点    } t = s->next;    //一开始让s指向twhile(t){s->next = r;    //原地逆置，让s指向r r = s;            //以下3句，是3个指针同时向后移动一位 s = t;t = t->next; } s->next = r;L2->next->next = NULL;//逆置后，原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2->next = s;    //此时s是逆置后链表的第一个结点，L2的头结点应该指向它 
}void merge(LinkList L,LinkList L2)    //将L与L2混合并合并 
{LinkList  pcur,p,q;pcur = L->next;    //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p = pcur->next;    //p指向L链表的第二个结点。p用来遍历L链表。 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;}
}void print_list(LinkList L)        //打印输出链表 
{L = L->next;while(L != NULL){printf("%3d",L->data);L = L->next;}printf("\n");
}int main()
{LinkList L;    //L是头指针 LinkList search;    //用来存储拿到的某一个结点 list_tail_insert(L);    //输入数据可以为数据 print_list(L);//链表打印LinkList L2=NULL;    find_middle(L,L2); //寻找中间结点，并返回第二条链表 。只有一个结点时，L2中是没有结点的 printf("-----------------------------\n");print_list(L);print_list(L2);printf("-----------------------------\n");reverse(L2);print_list(L2);printf("-----------------------------\n");merge(L,L2);free(L2);print_list(L);return 0; 
}