网站设计程序,有名的网页游戏,美团网站开发,宁波网站建设团队哪家好题目#xff1a; 4. 单链表相关经典算法OJ题3#xff1a;合并两个有序链表5. 循环链表经典应⽤-环形链表的约瑟夫问题6. 单链表相关经典算法OJ题5#xff1a;分割链表 接着我们介绍后面的三道题#xff0c;虽然代码变多了但我们的思路更加通顺了 4. 单链表相关经典算法OJ题… 题目 4. 单链表相关经典算法OJ题3合并两个有序链表5. 循环链表经典应⽤-环形链表的约瑟夫问题6. 单链表相关经典算法OJ题5分割链表 接着我们介绍后面的三道题虽然代码变多了但我们的思路更加通顺了 4. 单链表相关经典算法OJ题3合并两个有序链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/ 创建新链表遍历原链表将节点值小的进行尾插到新链表中 这里要多次进行对NULL的判断开始传入列表中间newHead的判断循环出来一个为NULL的判断 重复原因新链表存在空链表和非空两种情况 优化的方法 1.将重复的部分封装成一个函数 2.动态申请一个空间但这个空间部存储任何的信息 那么我们着重讲一下第二个方法
他的解决方法就是让新链表不为NULL 在创建时动态申请一块空间但不存储任何数据让NULL节点变为非NULL的节点这是就不用判断链表是不是为非NULL
但这时返回就不能将头节点直接返回而是要将头节点的下一个位置的地址返回 当然释放的空间还是要释放一下来使代码更加完善
/*** 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) {ListNode* l1 list1;ListNode* l2 list2;//判空if(list1 NULL){return list2;}if(list2 NULL){return list1;}ListNode* newHead,*newTail;//newHead newTail NULL;newHead newTail (ListNode*)malloc(sizeof(ListNode));while(l1 l2){if(l1-val l2-val){newTail-next l1;newTail newTail-next;l1 l1-next;}else{newTail-next l2;newTail newTail-next;l2 l2-next;}}//跳出循环有两种情况if(l2 ! NULL){newTail-next l2;}if(l1 ! NULL){newTail-next l1;}ListNode* ret newHead-next;free(newHead);newHead NULL;return ret;
}其实这样的链表叫带头链表这个“头”一般称作哨兵位
5. 循环链表经典应⽤-环形链表的约瑟夫问题
题目链接https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a 思路一用数组的方法先进行遍历然后将离开的人置为0然后不断循环遍历最中不为0的就是我们要的数据 思路二循环链表的方法 我们先介绍一下循环链表 这里涉及到循环链表其实也就是单链表但是尾部相连了 那么在创建和删除时要多注意就行了 循环数数将数到2的将其删除
这里就要使用前后指针 代码的难点就是创建循环链表
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param n int整型 * param m int整型 * return int整型*/#include stdio.h
typedef struct ListNode ListNode ;ListNode* buyNode(int x)//申请空间{ListNode* node (ListNode*)malloc(sizeof(ListNode));if(node NULL){exit(1);}node-val x;node-next NULL;return node;}ListNode* createCircle(int n)//创建带环链表{//创建第一个节点ListNode* phead buyNode(1);ListNode* ptail phead;for(int i 2; i n;i){ptail-next buyNode(i);ptail ptail-next;}ptail-next phead;return ptail;}
int ysf(int n, int m ) {// write code hereListNode* prev createCircle(n);ListNode* pcur prev-next;int count 1;while (prev-next ! pcur)//链表只有一个节点 {if(count m){//销毁先连接在销毁prev-next pcur-next;free(pcur);pcur prev-next;count 1;}else {prev pcur;pcur pcur-next;count;}}return pcur-val;
}6. 单链表相关经典算法OJ题5分割链表
题目链接https://leetcode.cn/problems/partition-list-lcci/description/ 思路一将原列表复制一份然后对大于等于x的进行操作先尾插后销毁 思路二或者创建一个新链表进行存储对大于的数进行尾插小于的进行头插 思路三创建两个新链表小链表和大链表 分成两个链表然后将两个链表连接起来 这里就是greaterHead后的指针不为NULL而是一个随机地址 将两个代码换过来就可以解决这个问题了
/*** 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(head NULL){return head;}ListNode* lessHead,*lessTail;ListNode* greaterHead,*greaterTail;lessHead lessTail (ListNode*)malloc(sizeof(ListNode));greaterHead greaterTail (ListNode*)malloc(sizeof(ListNode));//遍历原链表进行尾插ListNode* pcur head;while(pcur){if(pcur-val x){//小链表lessTail-next pcur;lessTail lessTail-next;}else{greaterTail-next pcur;greaterTail greaterTail-next;}pcur pcur-next;}//首尾相连greaterTail-next NULL;lessTail-next greaterHead-next;ListNode* ret lessHead-next;free(lessHead);free(greaterHead);lessHead greaterHead NULL;return ret;
}
