🔥博客主页:小王又困了
📚系列专栏:数据结构
🌟人之为学,不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
一、移除链表元素
💡方法一:
💡方法二:
二、链表的中间节点
💡方法一:
三、链表中倒数第k个结点
💡方法一:
四、反转链表
💡方法一:
💡方法二:
五、合并两个有序链表
💡方法一:
🗒️前言:
在上一期中我们给大家介绍了单链表,也了解了单链表的实现。接下来就让我们进入实践,练习一些经典题目,让我们对单链表的理解更加深入。
一、移除链表元素
题目:
💡方法一:
我们使用两个指针遍历数组,遇到与 val 相同的数据域,就删除这个节点。我们在思考问题时要想全面,当要删除头节点时,常规方法就无法实现,对于删除头节点要做单独处理。
🍩常规删除:
🍩头节点删除
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur!=NULL) { //删除 if(val==cur->val) { //头删 if(cur==head) { head=cur->next; free(cur); cur=head; } //常规 else { prev->next=cur->next; free(cur); cur=prev->next; } } //遍历 else { prev=cur; cur=cur->next; } } return head; }
💡方法二:
我们通过遍历,把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后,判断tail是否为空指针。
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newhead=NULL; struct ListNode* tail=NULL; struct ListNode* cur=head; while(cur) { if(cur->next==val) { //删除 struct ListNode* del=cur; cur=cur->next; free(del); } else { //尾插 if(tail==NULL) { newhead=tail=cur; //tail=cur; } else { tail->next=cur; tail=tail->next; } cur=cur->next; } } if(tail) { tail->next=NULL; } return newhead; }
二、链表的中间节点
题目:
💡方法一:
我们可以定义两个指针,快指针一次走两步,慢指针一次走一步,当快指针走到结尾时,慢指针正好走了一半,这样我们就可以找到中间节点。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast=head; struct ListNode* slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; }
三、链表中倒数第k个结点
题目:
💡方法一:
我们可以参考上一题的方法,同样定义快慢指针,想让快指针走k步,然后在同时走,走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点,所以我们要加入判断。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; while(k--) { //链表没有k步长 if(fast==NULL) { return NULL; } fast=fast->next; } while(fast!=NULL) { fast=fast->next; slow=slow->next; } return slow; }
四、反转链表
题目:
💡方法一:
我们定义三个指针n1,n2,n3,来改变节点链接的顺序。将头节点变为尾节点,当n2为空指针时,n1就为链表的头节点,只需返回n1就可以。两个指针倒方向,一个指针保持下一个。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1=NULL; struct ListNode* n2=head; struct ListNode* n3; if(n2) { n3=n2->next; } while(n2) { n2->next=n1; //往后走 n1=n2; n2=n3; if(n3) { n3=n3->next; } } return n1; }
💡方法二:
将链表的节点一个一个拿下来,进行头插。这里要注意赋值的顺序。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newnode=NULL; while(cur) { //保存节点 struct ListNode* next=cur->next; //头插 cur->next=newnode; newnode=cur; cur=next; } return newnode; }
五、合并两个有序链表
题目:
💡方法一:
我们创建一个带哨兵位的链表,这样在尾插时就不用判断是否是第一个节点,可以提高效率。要记住在最后要将哨兵位的空间释放。文章来源:https://www.toymoban.com/news/detail-627873.html
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=NULL; struct ListNode* tail=NULL; //创建一个哨兵位 head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); while(list1&&list2) { if(list1->val<list2->val) { tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } struct ListNode* del=head; head=head->next; free(del); return head; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位读者三连支持。文章有问题可以在评论区留言,博主一定认真认真修改,以后写出更好的文章。你们的支持就是博主最大的动力。文章来源地址https://www.toymoban.com/news/detail-627873.html
到了这里,关于【数据结构】单链表OJ题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!