网站如何添加统计代码是什么意思,营销网站建站企业,凡客网站设计,网片生产厂家前言 题目链接 移除链表元素 链表的中间结点 反转链表 分割链表 环形链表的约瑟夫问题 欢迎关注个人主页#xff1a;逸狼 创造不易#xff0c;可以点点赞吗~ 如有错误#xff0c;欢迎指出~ 移除链表元素
题述
给你一个链表的头节点 head 和一个整数 val #xff0c;请… 前言 题目链接 移除链表元素 链表的中间结点 反转链表 分割链表 环形链表的约瑟夫问题 欢迎关注个人主页逸狼 创造不易可以点点赞吗~ 如有错误欢迎指出~ 移除链表元素
题述
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点
思路1直接删除原链表中不符合的节点
遍历原链表遇到val就执行删除操作 执行删除操作修改指针的指向有点麻烦还有其他办法
思路2满足要求的节点放在新链表上
定义新链表利用pcur遍历原链表找不为val的节点尾插在新链表中 新链表newHead newTail
要考虑链表是否为空 链表为空插入进来的节点就是链表的头节点和尾节点 链表不为空插入进来的节点就是链表的新的尾节点
代码实现思路2 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//定义新链表的头尾指针ListNode* newHead,* newTail;newHeadnewTailNULL;ListNode* pcurhead;while(pcur){//不是val,尾插到新链表if(pcur-val!val){//链表为空if(newHeadNULL){newHeadnewTailpcur;}else{//链表不为空newTail-nextpcur;newTailnewTail-next;//}}//pcur继续往下走pcurpcur-next;}if(newTail)//要先判断newTail本来是否为空{newTail-nextNULL;}return newHead;
} 链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点 思路1统计链表中节点的个数通过除2找到中间节点
for(统计链表个数 for(根据除2结果走到中间节点)
思路2快慢指针
slow指针每次走1步fast走2步 当fast-next或者fast走到为空则slow刚好指向的就是中间节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* fast,*slow;fastslowhead;while(fastfast-next)//条件fast和fast-next不能相反会造成短路{slowslow-next;//slow走1步fastfast-next-next;//fast走2步}return slow;
} 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路1
创建新链表遍历原链表的节点将其插入到新链表中
思路2创建3个指针
分别记录前驱节点当前节点后继节点改变原链表的指向1 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//要先处理空链表if(headNULL){return head;}ListNode *n1,*n2,*n3;n1NULL;n2head;n3head-next;while(n2){//修改n2的指向n2-nextn1;//n1,n2,n3往下走n1n2;n2n3;if(n3)//要先判断n3不为空才能往下走{n3n3-next;}}return n1;
} 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 NULL)return list2;if (list2 NULL)return list1;ListNode *l1, *l2;l1 list1, l2 list2;//创建头节点ListNode *newHead, *newTail;newHead newTail (ListNode*)malloc(sizeof(ListNode));while (l1 l2) {if (l1-val l2-val) {// l1小l1上但要先判断l1不为空指针// if (newHead NULL)// newHead newTail l1;// else {// newTail-next l1;// newTail newTail-next;// }// l1 l1-next;//代码优化newTail-nextl1;newTailnewTail-next;l1l1-next;} else {// l2小// if (newHead NULL)// newHead newTail l2;// else {// newTail-next l2;// newTail newTail-next;// }// l2 l2-next;//代码优化newTail-nextl2;newTailnewTail-next;l2l2-next;}}if (l1) {newTail-next l1;}if (l2) {newTail-next l2;}return newHead-next;
}
分割链表 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 思路
定义2个链表大链表和小链表遍历原链表的节点将其放到对应的新链表中最将大小链表首尾相连
创建大小链表都要先创建一个哨兵位
利用pcur遍历链表 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(headNULL)return head;//创建带头的大小链表ListNode* lessHead ,*lessTail;ListNode* greaterHead,*greaterTail;lessHeadlessTail(ListNode*)malloc(sizeof(ListNode));greaterHeadgreaterTail(ListNode*)malloc(sizeof(ListNode));//遍历原链表将节点放在对应的新链表中ListNode*pcurhead;while(pcur){if(pcur-val x){//放在小链表中lessTail-nextpcur;lessTaillessTail-next;}else{//放在大链表中greaterTail-nextpcur;greaterTailgreaterTail-next;}pcurpcur-next;}//大链表尾要置为空greaterTail-nextNULL;//大小链表首尾相连lessTail-nextgreaterHead-next;ListNode*retlessHead-next;free(greaterHead);free(lessHead);return ret;
}
环形链表的约瑟夫问题 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后只剩下一个人问最后留下的这个人编号是多少、 代码实现 //这道OJ题已经创建好了结构体结点只是没有展示出来typedef struct ListNode ListNode;
//申请新节点
ListNode* BuyNode(int x)
{ListNode* newNode(ListNode*)malloc(sizeof(ListNode));//可写可不写一般不会申请失败if(newNodeNULL){exit(1);}newNode-valx;newNode-nextNULL;return newNode;
}
//创建循环链表
ListNode*createList(int n)
{//创建头节点ListNode* pheadBuyNode(1);ListNode* ptailphead;//从2开始共创建了n个节点for(int i2;in;i){ptail-nextBuyNode(i);ptailptail-next;}//链表要首尾相连循环起来ptail-nextphead;return phead;
}
int ysf(int n, int m ) {//创建不带头单向循环链表//逢m删除节点ListNode*headcreateList(n);ListNode*pcurhead;ListNode*prevNULL;//用于记录pcur走过的位置,是pcur的前驱节点int count1;//逢m删除节点while(pcur-next!pcur)//表示删除节点到只剩下自己跳出循环{if(countm){//删除当前节点pcurprev-nextpcur-next;free(pcur);//删除pcur节点后要让pcur走到新的位置count置为初始值pcurprev-next;count1;}else {//pcur往后走prevpcur;pcurpcur-next;count;}}//此时pcur节点就是幸存下来的节点return pcur-val;
}
