做背景音乐的版权网站,怎么能够找到免费的网址,网站制作百度网盘,优书网书单推荐1. 移除链表元素 OJ链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 本题是说给出一个链表的头节点head和一个整数val#xff0c;如果发现节点中存的数据有val就删掉它#xff0c;最后返回修改后的链表头节点地址 如果题目中没有明确…1. 移除链表元素 OJ链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 本题是说给出一个链表的头节点head和一个整数val如果发现节点中存的数据有val就删掉它最后返回修改后的链表头节点地址 如果题目中没有明确提及给出的链表是否是带头的那就默认是不带头的链表此时题目中再提到头节点就是指链表的第一个节点
思路1 从第二个节点开始判断其内含的数据是否是val然后遍历链表最后判断头节点中数据是否是val如果是再挪移头节点的指向 至于为什么从第二个节点开始扫描是为了不用每次都判断一下头节点要不要移动先把后面的节点都处理好最后再确定头节点的指向 但是这个思路还是太复杂了
思路2 创建一个新链表把不是val的节点都丢到新链表中去最后返回新链表的头节点 与其说是创建了一个新链表不如说是将原链表的链接顺序拿到一个新的地方进行更改
struct ListNode* removeElements(struct ListNode* head, int val)
{//记录新链表的头和尾struct ListNode* newhead NULL;struct ListNode* newtail NULL;//pcur用来扫描原链表struct ListNode* pcur head;while (pcur){//不是val尾插到新链表的尾if (pcur-val ! val){//如果新链表为空那么新加入的节点既是头节点也是尾节点if (newhead NULL){newhead pcur;newtail pcur;}//如果链表不为空就将新节点放到链表尾,else{newtail-next pcur;newtail pcur;}}//pcur指向的节点是不是val都要往下走pcur pcur-next;}//因为有可能返回的是空链表所以不能粗暴的去访问newtail-next//要先判断要返回的newtail是否为空也就是说是否是空链表if (newtail){newtail-next NULL;}return newhead;
} 2. 链表的中间结点 OJ链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 本题是说给出一个链表的头节点head然后找到这个链表的中间节点如果有两个中间节点就返回第二个中间节点
思路1 遍历整个链表数出一共有几个节点然后通过除2找到中间节点的下标然后通过下标再访问出中间节点的地址 很明显这个方法很麻烦
思路2快慢指针法 跟前面双指针那节一样这个快慢指针也不是真正的创造两个指针而是创造两个具有类似指针功能的变量 思路就是创造一个慢指针slow一个快指针fast然后slow走一步fast走两步这样fast走完的时候slow刚好来到链表中间 快慢指针法就是通过只遍历一次就能达到对整体进行类似除法运算的功效比如slow走1步fast走4步fast走完slow就走到整体的四分之一处 回到本题在判断结束扫描的条件时要注意先判断fast是否为NULL利用短路的特性避免判断fast-next因为如果fast为假了去访问next的时候就会崩
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;//有一个为假就跳出循环while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
} 3. 反转链表 OJ链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 本体是说给一个单链表的头节点地址head让反转链表再将新链表的头返回值得注意的是这个链表可能是个空链表
思路1 和第一题类似创建一个新链表每次将旧链表的第一个节点拿下来头插到新链表 因为这题给的是单链表不能用后面的节点访问前面的节点所以不要想从最后一个节点开始改变链接方向因为遍历到最后一个节点就找不到前面的节点了
思路2 用3个指针n1、n2、n3初始状态n1指向空n2指向头节点n3指向第二个节点。然后将n2节点的指向变成n1然后把n1变到n2的位置n2变到n3的位置再把n3滑到下一个节点。然后在n2不为空的情况下一直循环这个操作。
struct ListNode* reverseList(struct ListNode* head)
{//如果传过来的是空链表if (head NULL){return head;}struct ListNode* n1 NULL;struct ListNode* n2 head;struct ListNode* n3 head-next;while (n2){n2-next n1;n1 n2;n3 n2;//如果n3已经指向NULL了就不用往下滑了if (n3){n3 n3-next;} }return n1;
} 4. 合并两个有序链表 OJ链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 本题是说给两个升序链表的头节点地址list1和list2然后将两个链表合并成一共新的升序链表并返回新链表的头值得注意的是给出的两个链表可能有空的
思路 创建一个新链表再用顺序表中讲到的那道合并数组的题的思想
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//如果给出的某个链表为空就返回另一个链表if (list1 NULL){return list2;}if (list2 NULL){return list1;}//两个扫描原链表的指针struct ListNode* p1 list1;struct ListNode* p2 list2;//两个控制新链表的指针struct ListNode* newhead NULL;struct ListNode* newtail NULL;//p1或p2有一个扫描完就退出循环while (p1 p2){//如果p1扫到的数据更小if (p1-val p2-val){//如果新链表中没有节点if (newhead NULL){newhead p1;newtail p1;}//如果新链表不为空else{newtail-next p1;newtail p1;}p1 p1-next;}//如果p2扫到的数据更小else{//如果新链表为空if (newhead NULL){newhead p2;newtail p2;}//如果新链表不为空else{newtail-next p2;newtail p2;}p2 p2-next;}}//处理旧链表没挪完的那部分if (p1){newtail-next p1;}if (p2){newtail-next p2;}return newhead;
} 5. 分割链表(带头链表的优势) 本题我会距离说明带头链表比不带头链表好在哪里 OJ链接https://leetcode.cn/problems/partition-list-lcci/description/ 本题给出一个链表的头节点地址和一个特定的值x要求是把所存数据小于x的节点堆在前面把大于等于x的节点堆在后面堆放的时候不需要保存节点原来相对位置的有关信息
思路1 创建一个新链表把原链表中小于x的节点头插把大于等于x的节点尾插
思路2带头链表的优点 先说解题思路我们创造两个新链表lesshead尾插小于x的节点bighead尾插大于等于x的节点最后把bighead连到lesshead后面 现在我们回忆一下之前的代码再每次插入新节点的时候都要判断一下链表是否为空这很麻烦。所以我们直接让链表带头这样每次插入新节点的时候就不用判断了因为链表一定不为空它有一个不存储数据的头或者说哨兵位省去了插入时的很多麻烦
struct ListNode* partition(struct ListNode* head, int x)
{//判断传过来的是否时空链表if (head NULL){return head;}//创建两个带头新链表struct ListNode* lesshead, * lesstail;struct ListNode* bighead, * bigtail;//申请头节点空间并将其地址记录lesshead lesstail (struct ListNode*)malloc(sizeof(struct ListNode));bighead bigtail (struct ListNode*)malloc(sizeof(struct ListNode));//用pcur遍历原链表将节点放到对应的新链表中struct ListNode* pcur head;while (pcur){if (pcur-val x){lesstail-next pcur;lesstail lesstail-next;}else{bigtail-next pcur;bigtail bigtail-next;}pcur pcur-next;}//链接两个链表//先将大链表的尾置空bigtail-next NULL;//再接上注意要掠过大链表的那个没意义的头lesstail-next bighead-next;//先存上小链表的第一个存有效数据的节点struct ListNode* ret lesshead-next;//在释放两个新链表的头free(bighead);free(lesshead);return ret;
} 6. 环形链表的约瑟夫问题 OJ链接环形链表的约瑟夫问题_牛客题霸_牛客网 本题······哎呀这题我就不复述了人家题干说的挺清楚的
思路循环链表 创建不带头单向循环链表模拟围成一圈的人逢m就删除节点
#includestdlib.h
//创建新节点
struct ListNode* BuyNode(int x)
{struct ListNode* newnode (struct ListNode*)malloc(sizeof(struct ListNode));newnode-val x;newnode-next NULL;return newnode;
}
//创建链表
struct ListNode* creatlist(int n)
{//先创建一个头节点struct ListNode* phead BuyNode(1);struct ListNode* ptail phead;//再循环进行尾插形成链表for (int i 2; i n; i){ptail-next BuyNode(i);ptail ptail-next;}//让链表首尾相连ptail-next phead;return phead;
}int ysf(int n, int m)
{//创建不带头单向循环链表struct ListNode* phead creatlist(n);struct ListNode* pcur phead;struct ListNode* prev NULL;//逢m删除节点,直到剩下最后一个节点int count 1;while (pcur-next ! pcur){if (m count){//删除当前节点prev-next pcur-next;free(pcur);count 1;pcur prev-next;}else{//pcur往后走prev pcur;pcur pcur-next;count;}}return pcur-val;
} 不必担心当 m1 的使得 prev-next 非法的情况while的循环条件就已经把这种情况挡在外面了而且题干里说了一定会剩下来一个人所以返回pcur的数据也是没有问题的。
