✅作者简介：大家好我是zoroxs
📃个人主页：c/c++学习之路
🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦
链表OJ
本文是带读者做一些常见的链表OJ题,检验一下自己的链表是否基础扎实
📕删除链表中等于给定值 val 的所有节点 (leetcode 203)
分析
看到这个题,大家一定会想到的思路就是
1.创建一个新的头节点,不是val的就尾插下来, 把是val的 free 掉.
有几种特殊情况需要特殊处理,
- 链表为空,直接返回NULL
- 链表中所有的值都是val ,一样也是返回NULL
大家可以自己推导一下执行过程,数据结构学习的过程必须要画图和思考,画图比写代码困难.
所以我们找到第一个不是val的节点之后,就可以继续向后找
下面看代码
structListNode*removeElements(structListNode* head,int val){if(NULL== head){returnNULL;}structListNode* cur = head;//1.找到第一个不是val的结点while(cur && cur->val == val){structListNode* next = cur->next;free(cur);
cur = next;}//判断循环以哪种方式结束, 如果NULL == cur,说明链表中的值都等于val 直接返回NULL;if(NULL== cur){returnNULL;}//走到这里, cur的位置就是第一个值 != val 的节点structListNode* newHead = cur;structListNode* newTail = cur;//当前cur位置已经给到了newHead和newTail , 所以cur需要往后指一个
cur = cur->next;while(cur){structListNode* next = cur->next;//1.如果相等,继续释放if(val == cur->val){free(cur);}else//2.不相等就尾插{
newTail->next = cur;
newTail = newTail->next;}
cur = next;}//把尾指向的置空
newTail->next =NULL;return newHead;}
📗反转一个单链表 (leetcode 206)
1️⃣思路一
定义一个新的头节点,把原链表中的每一个元素头插进去,得到的就是反转后的链表
学习数据结构的时候,一定要画图,画图,一步步用图来执行,就把伪代码同样写出来了
来看一下代码实现
structListNode*reverseList(structListNode* head){if(NULL== head){returnNULL;}structListNode* cur = head;structListNode* newHead =NULL;while(cur){structListNode* next = cur->next;
cur->next = newHead;
newHead = cur;
cur = next;}return newHead;}
2️⃣思路二
这不就是我们想要的结果吗
大家来看代码
structListNode*reverseList(structListNode* head){if(NULL== head){return head;}structListNode* cur = head;structListNode* prev =NULL;while(cur){structListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;}return prev;}
大家一定要画图+ 思考,代码很简单,关键是画图模拟执行流程
📘给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点
看到这个题,大家很容易想到的思路就是
计算链表的长度,然后算出长度的一半,从头开始走,走一半,刚好是中间节点
这个方法固然可以做,我在这里就不实现了,大家可以自己尝试一下,不难
这里给大家提出一种新的思路,玩链表必会,快慢指针
我们定义两个指针 ,fast slow ,都从头开始走, fast一次走两步, slow 一次走一步, 当fast走到结尾的时候,slow是不是刚好走到中间位置呢
我们来分析一下
看一下代码
structListNode*middleNode(structListNode* head){if(NULL== head){returnNULL;}structListNode* fast = head;structListNode* slow = head;//因为fast一次走两步, 所以fast->next也不能为空,不然会有空指针异常while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;}//返回慢指针return slow;}
📙输入一个链表，输出该链表中倒数第k个结点
看到这个题,第一个想到的还是算链表的长度,然后找到倒数第k个节点,虽然复杂度也是O(N)
但是我们了解了快慢指针,就可以朝着这方面去想
定义两个指针,fast slow
来看一下代码
structListNode*FindKthToTail(structListNode* pListHead,int k ){//判断链表是否为空if(NULL== pListHead){returnNULL;}//判断k是否合法if(k <=0){returnNULL;}structListNode* fast = pListHead;structListNode* slow = pListHead;//让fast先走k步while(k--){//如果k大于链表的长度,那么这里fast会变成空if(NULL== fast){returnNULL;}
fast = fast->next;}//他俩同时走,fast为空的时候,slow就是结果while(fast){
slow = slow->next;
fast = fast->next;}return slow;}
📓将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
相信大家看到这个题一定不陌生,肯定做过一道题,两个有序数组合并成一个数组,没做过的可以去做一个.
这里用的思想和那个一样, 都是归并, 只不过链表这里不需要开辟新的空间
我们可以使用malloc 开辟一个哨兵位的头结点,不存储有效数据,来方便操作,但是使用完了之后一定要记得释放
分析一下
直接来看代码
structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(NULL== list1){return list2;}if(NULL== list2){return list1;}structListNode* cur1 = list1;structListNode* cur2 = list2;structListNode* newHead =(structListNode*)malloc(sizeof(structListNode));structListNode* newTail = newHead;while(cur1 && cur2){if(cur1->val < cur2->val){//把cur1尾插到新链表structListNode* next = cur1->next;
newTail->next = cur1;
newTail = newTail->next;
cur1 = next;}else{//把cur2尾插到新链表structListNode* next = cur2->next;
newTail->next = cur2;
newTail = newTail->next;
cur2 = next;}}//走到这里,说明有一个链表已经结束if(cur1){//直接把剩下的拼接过去
newTail->next = cur1;}if(cur2){//直接把剩下的拼接过去
newTail->next = cur2;}structListNode* next = newHead->next;free(newHead);return next;}
📔编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
看到这个题,做题选项没有C语言,所以选了c++ ,因为c++是兼容C语言的
首先要求是不能改变原来的顺序,如果可以改变我们可以怎么解??
弄一个新链表,小于x的就头插过去,其他的尾插过去就可以解了
这里要求顺序,我们可以定义两个新的链表,开辟两个哨兵位,不存储数据,
一个尾插小于x的,另一个尾插其他的, 然后把两个链表拼接起来就OK了
如果不把greaterTail置空,就会成环
看代码
classPartition{public:
ListNode*partition(ListNode* pHead,int x){if(NULL== pHead){returnNULL;}
ListNode* lessHead =(ListNode*)malloc(sizeof(ListNode));
ListNode* greaterHead =(ListNode*)malloc(sizeof(ListNode));
ListNode* lessTail = lessHead;
ListNode* greaterTail = greaterHead;
ListNode* cur = pHead;while(cur){
ListNode* next = cur->next;if(cur->val < x){//尾插到less链表
lessTail->next = cur;
lessTail = lessTail->next;
cur = next;}else{//尾插到greater链表
greaterTail->next = cur;
greaterTail = greaterTail->next;
cur = next;}}//拼接起来
lessTail->next = greaterHead->next;//避免成环
greaterTail->next =NULL;//释放空间free(greaterHead);
ListNode* next = lessHead->next;free(lessHead);return next;}};
📒链表的回文结构
看到这个题,非常熟悉吧,什么回文字符串,回文数字… 现在变成了回文链表
因为是单向无头不循环链表,所以无法往前找,所以就得想别的方法
这里要求时间复杂度O(n) ,空间复杂度为O(1)
最初的思路是,先正向把链表中的值挨个放到一个数组中,然后反转链表,挨个对比
但是这样会开辟一个数组,长度和链表长度一样, 虽然题目说链表长度小于900,但是空间复杂度是O(N)
我们想一下前面做的题,我们可不可以找到中间节点,然后把中间节点之后的反转一下,这不就是刚好可以两个链表比较了吗
我们来分析一下
我们来用代码实现一下
classPalindromeList{public:boolchkPalindrome(ListNode* A){if(NULL== A){returnfalse;}//1.找中间节点
ListNode* fast = A;
ListNode* slow = A;while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;}//slow当前指向的是中间节点//2.反转链表
ListNode* cur = slow;
ListNode* midHead =NULL;while(cur){
ListNode* next = cur->next;
cur->next = midHead;
midHead = cur;
cur = next;}//反转结束,中间链表的头是midHead
cur = A;
ListNode* mid_cur = midHead;while(mid_cur)//以中间链表的结束为标记{if(cur->val != mid_cur->val){returnfalse;}
cur = cur->next;
mid_cur = mid_cur->next;}returntrue;}};
📚输入两个链表，找出它们的第一个公共结点
看到这个题,首先就能想到的解法是O(N^2),A的节点挨着去B链表中找,这样可以实现,但是复杂度过高,过于浪费时间,大家可以自己实现一下
在这里,我们可以把问题分解成2个问题
- 判断链表是否相交
- 如果链表相交返回交点,不相交返回NULL
我们首先想一下如何能判断链表是否相交
注意到,链表相交的最后结果,是两个链表交到一起,就像两个水流汇在一起,所以他们的最后一个节点一定是相同的
所以我们可以这样判断:
如果两个链表最后一个节点相同,那么他们一定相交,反之则不然
那么如果相交的话,如何判断交点呢?
如果是这样的两个链表,我们很容易找到交点
因为长度相同,只需要并行往后走,就可以找到交点
如果链表相交,那么后半部分一定是相同的,所以只需要操作前半部分
我们可以计算链表的长度,让长的链表先走 长度差值步,然后再一起走,不就相当于并行了么
看一下代码
structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){if(NULL== headA ||NULL== headB){returnNULL;}//1.判断是否相交,顺便求出两个链表长度int lenA =0;int lenB =0;structListNode* curA = headA;structListNode* curB = headB;//找尾while(curA->next){
lenA++;
curA = curA->next;}while(curB->next){
lenB++;
curB = curB->next;}//判断是否相交if(curA != curB){//说明没有交点returnNULL;}//寻找交点,让长链表先走差值步//假设a长structListNode* l1 = headA;structListNode* l2 = headB;if(lenA < lenB){
l1 = headB;
l2 = headA;}int tmp =abs(lenA-lenB);while(tmp--){//让长链表先走差值步
l1 = l1->next;}//并行while(l1 != l2){
l1 = l1->next;
l2 = l2->next;}return l1;}
📃给定一个链表，判断链表中是否有环。
这个题的思路可以有很多,有破解版–>如果链表走了10000多次还没停下来,说明有环(不正经解法)
第二种 我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
我们这里采用另一种,龟兔赛跑(快慢指针).
定义两个指针,一个为fast 一个为slow ,如果链表中有环,他俩一定会相遇
请看证明过程
我们来看一下代码
bool hasCycle(structListNode*head){if(NULL== head){returnNULL;}structListNode* fast = head;structListNode* slow = head;while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;//说明追上了if(fast == slow){return true;}}return false;}
大家应该有些疑问,为什么fast要走两步,fast走3步,fast走4步不行吗? 走n步呢??
📃给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
这个题一眼看过去,没有思路,我们画图慢慢分析一下
1️⃣思路一
我们来写一下代码
structListNode*detectCycle(structListNode*head){if(NULL== head){returnNULL;}//判断是否有环structListNode* fast = head;structListNode* slow = head;while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;if(fast == slow){//相遇节点 ,以meet为新的结尾,变成两个链表求交点的问题structListNode* meet = fast;structListNode* next = meet->next;
meet->next =NULL;returngetIntersectionNode(head, next);}}returnNULL;}
2️⃣思路二
这里还有另一种思路
一个从相遇节点meetNode往后走,另一个从头开始走,他们会在环的入口点相遇
我们来证明一下
所以一个从头开始走,另一个从meetNode开始走,会在环的入口点相遇
看代码
structListNode*detectCycle(structListNode*head){if(NULL== head){returnNULL;}//判断是否有环structListNode* fast = head;structListNode* slow = head;while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;//说明fast追上slow-->有环if(fast == slow){//相遇节点structListNode* meet = fast;structListNode* cur = head;//相遇节点往下走,与头结点往后走,会在环的入口相遇while(meet != cur){
meet = meet->next;
cur = cur->next;}return meet;}}returnNULL;}
📚8.总结
学习数据结构的过程中,一定要画图与思考并进,多思考多画图,多写代码
如果大家有什么问题,可以私信我
🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦
版权归原作者 Zoroxs 所有， 如有侵权，请联系我们删除。