在了解了链表的相关知识后我们还需要一些题目进行练习加深对链表这方面知识的理解也可以用来检测链表这块学的的怎么样废话不多说开始上手。

一、移除链表元素

ListNode*bNULL;if(headNULL)return

head;while(head){if(head-val!val){if(aNULL)abhead;else{b-nex***ad;bb-next;}}headhead-next;}if(b)b-nextNULL;return

首先如果链表本身为空就可以直接返回一个空指针如果不为空就可以开始下一个阶段先创建两个指针a,b指向开始给的头结点让初始头结点开始遍历如果遇到节点值为特定值就让b节点指向初始头结点的下一个相当于跳过了这个节点最后遍历完如果b节点不为空就将b的下一个节点置空相当于是把那些带有特定值的节点删除了。

二、反转链表

ListNode*n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return

n1;

首先还是要判断链表是否为空空链表直接返回就行了这里需要创建三个指针在遍历链表时将当前节点的

next

指针改为指向前一个节点由于节点没有引用其前一个节点因此必须事先存储其前一个节点在更改引用之前还需要存储后一个节点最后返回新的头引用。

三、合并两个有序链表

这道题让我们把两个有序链表合并在一起并且合并后的链表依然有序这里先上代码后面讲解。

/***

ListNode*n2n1;while(list1list2){if(list1-vallist2-val){n2-nextlist1;list1list1-next;n2n2-next;}else{n2-nextlist2;list2list2-next;n2n2-next;}}if(list1)n2-nextlist1;if(list2)n2-nextlist2;struct

ListNode*cn1-next;free(n1);n1NULL;return

首先判断两个有序链表中是否有空链表如果有一方为空链表就可以直接返回另一个链表了需要开辟一个新的链表将两个链表的每一个值一一比较排个序再一个一个的放入新的链表当中。

head

这道题可以用很多种方式写出来这里用的是快慢指针的方式还有计数器法等方式计数器法就是先遍历一遍链表算出有多少个节点再除以二按照除后的数字在遍历一遍到中间节点位子这里快慢指针法就先上代码后面讲解。

/***

i0;while(head){headhead-next;i;}int

counti/2;while(count0){aa-next;count--;}return

让俩个指针开始时同时指向头结点一个一次走一步一个每次走两步在快指针到达尾节点或者空节点时奇数节点链表和偶数节点链表会不一样慢指针就会在中间节点的位置奇数节点指针会在中间节点偶数节点指针会在中间两个节点的后一个节点最后输出慢指针就行了。

题目链接约瑟夫问题

#includestdlib.h#includestdio.h

typedef

{music*a(music*)malloc(sizeof(music));a-datan;a-nextNULL;return

music*creat(int

{music*ainitial(1);music*ba;for(int

i2;in;i){b-nextinitial(i);bb-next;}b-nexta;return

int

{music*acreat(n);music*heada-next;int

count1;while(head-next!head){if(countm){a-nex***ad-next;free(head);heada-next;count1;}else{ahead;headhead-next;count;}}return

head-data;

这道题涉及到了链表的创建所以就需要一个包含数据成员的结构体以及初始化函数和创建链表相关函数在实现约瑟夫问题的函数中先创建head和a指针head指针就是扮演着正在报数的那个人a这是head的前一个节点当报数的head报道特定的数字,a就会跳过这个节点然后再把这个节点释放掉head继续在a-next循环着操作留下最后一个就可以输出结果了。

本篇内容就到这里了没到题目都给了链接可以自己去尝试解题光听的话效果没那么好。