个人怎么制作网站,定制vx怎么弄,thinkphp开源cms系统,营销策划主题目录
前言
一、移除链表元素
二、反转链表
三、合并两个有序链表
四、链表的中间节点
五、环形链表的约瑟夫问题 前言 在了解了链表的相关知识后#xff0c;我们还需要一些题目进行练习加深对链表这方面知识的理解#xff0c;也可以用来检测链表这块学的的怎么样#…目录
前言
一、移除链表元素
二、反转链表
三、合并两个有序链表
四、链表的中间节点
五、环形链表的约瑟夫问题 前言 在了解了链表的相关知识后我们还需要一些题目进行练习加深对链表这方面知识的理解也可以用来检测链表这块学的的怎么样废话不多说开始上手。
一、移除链表元素 这里给上题目链接感兴趣的可以看一下移除链表元素 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回新的头节点 。 看题目描述我们需要删除链表中链表节点为特定值的节点。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*aNULL;struct ListNode*bNULL;if(headNULL)return head;while(head){if(head-val!val){if(aNULL)abhead;else{b-nexthead;bb-next;}}headhead-next;}if(b)b-nextNULL;return a;
} 首先如果链表本身为空就可以直接返回一个空指针如果不为空就可以开始下一个阶段先创建两个指针a,b指向开始给的头结点让初始头结点开始遍历如果遇到节点值为特定值就让b节点指向初始头结点的下一个相当于跳过了这个节点最后遍历完如果b节点不为空就将b的下一个节点置空相当于是把那些带有特定值的节点删除了。
二、反转链表 这里先给上题目链接反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 这里先给上代码慢慢来讲解一下。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {if(headNULL)return head;struct ListNode*n1NULL;struct ListNode*n2head;struct ListNode*n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
} 首先还是要判断链表是否为空空链表直接返回就行了这里需要创建三个指针在遍历链表时将当前节点的 next 指针改为指向前一个节点由于节点没有引用其前一个节点因此必须事先存储其前一个节点在更改引用之前还需要存储后一个节点最后返回新的头引用。
三、合并两个有序链表 题目链接合并有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 这道题让我们把两个有序链表合并在一起并且合并后的链表依然有序这里先上代码后面讲解。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1NULL)return list2;if(list2NULL)return list1;struct ListNode*n1(struct ListNode*)malloc(sizeof(struct ListNode));struct 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 c;
} 首先判断两个有序链表中是否有空链表如果有一方为空链表就可以直接返回另一个链表了需要开辟一个新的链表将两个链表的每一个值一一比较排个序再一个一个的放入新的链表当中。
四、链表的中间节点 题目链接链表的中间节点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 这道题可以用很多种方式写出来这里用的是快慢指针的方式还有计数器法等方式计数器法就是先遍历一遍链表算出有多少个节点再除以二按照除后的数字在遍历一遍到中间节点位子这里快慢指针法就先上代码后面讲解。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*ahead;int i0;while(head){headhead-next;i;}int counti/2;while(count0){aa-next;count--;}return a;
}
让俩个指针开始时同时指向头结点一个一次走一步一个每次走两步在快指针到达尾节点或者空节点时奇数节点链表和偶数节点链表会不一样慢指针就会在中间节点的位置奇数节点指针会在中间节点偶数节点指针会在中间两个节点的后一个节点最后输出慢指针就行了。
五、环形链表的约瑟夫问题 题目链接约瑟夫问题 描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后只剩下一个人问最后留下的这个人编号是多少 示例 输入 5,2 返回值 3 说明 开始5个人 12345 从1开始报数1-12-2编号为2的人离开 1345从3开始报数3-14-2编号为4的人离开 135从5开始报数5-11-2编号为1的人离开 35从3开始报数3-15-2编号为5的人离开 最后留下人的编号是3 先上代码后面慢慢讲解。
#includestdlib.h#includestdio.h
typedef struct music
{int data;struct music* next;
}music;
music*initial(int n)
{music*a(music*)malloc(sizeof(music));a-datan;a-nextNULL;return a;
}
music*creat(int n)
{music*ainitial(1);music*ba;for(int i2;in;i){b-nextinitial(i);bb-next;}b-nexta;return b;
}
int ysf(int n, int m ) {music*acreat(n);music*heada-next;int count1;while(head-next!head){if(countm){a-nexthead-next;free(head);heada-next;count1;}else{ahead;headhead-next;count;}}return head-data;
} 这道题涉及到了链表的创建所以就需要一个包含数据成员的结构体以及初始化函数和创建链表相关函数在实现约瑟夫问题的函数中先创建head和a指针head指针就是扮演着正在报数的那个人a这是head的前一个节点当报数的head报道特定的数字,a就会跳过这个节点然后再把这个节点释放掉head继续在a-next循环着操作留下最后一个就可以输出结果了。 本篇内容就到这里了没到题目都给了链接可以自己去尝试解题光听的话效果没那么好。
