单链表-C语言
- C语言
- 2024-04-13
- 8102热度
- 0评论
单链表-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;
};
时间复杂度
让我们逐个分析每个子函数的时间复杂度:
-
list_tail_insert(): 这个函数的时间复杂度取决于输入的元素数量。在每次循环中,我们分配了一个新的结点并将其链接到链表的末尾。假设有 ( n ) 个元素,则时间复杂度为 ( O(n) ),其中 ( n ) 是元素的数量。
-
PrintList(): 这个函数只是简单地遍历整个链表并打印每个元素。因为它只遍历一次链表,时间复杂度是 ( O(n) ),其中 ( n ) 是链表中的元素数量。
-
find_middle(): 在这个函数中,我们使用了一种双指针技巧来找到链表的中间结点。由于我们只遍历了链表一次,因此时间复杂度是 ( O(n) ),其中 ( n ) 是链表中的元素数量。
-
reverse(): 这个函数用于将链表原地逆转。它遍历了整个链表一次,并且对于每个结点,只有常数次操作。因此,时间复杂度是 ( O(n) ),其中 ( n ) 是链表中的元素数量。
-
merge(): 这个函数用于合并两个链表。在这个函数中,我们遍历了两个链表中的元素,并且对于每个元素只有常数次操作。因此,时间复杂度也是 ( O(n) ),其中 ( n ) 是两个链表中的元素数量之和。
因此,最终算法的时间复杂度主要由 list_tail_insert()、find_middle()、reverse() 和 merge`()函数的时间复杂度决定,它们都是 ( O(n) )。因此,最终算法的时间复杂度是 ( O(n) ),其中 ( n ) 是输入链表中的元素数量。