🎁个人主页:我们的五年
🔍系列专栏:每日一练
🌷追光的人,终会万丈光芒
目录
🏝问题1:反转链表
⛷问题描述:编辑
⛷ 问题分析:
⛷代码实现:
🏝问题2:寻找链表的中间节
⛷问题描述:
⛷问题分析:
⛷代码实现:
🏝问题3:返回单链表的倒数第K个节点的值
⛷问题描述:
⛷问题分析:
⛷代码实现:
🏝问题4:合并两个有序链表
⛷问题描述:
⛷问题分析:
⛷代码实现:
前言:
这篇文章会给大家带来几道经典的单链表题目,这些题目的步骤,可能会在一些难的题目中作为基本步骤,也就是难的题目也会应用到这些思想。
比如:
反转一个单链表,寻找一个单链表的中间节点,找到单链表的倒数第K个节点等。
🏝问题1:反转链表
【LeetCode】链接:. - 力扣(LeetCode)
⛷问题描述:
⛷ 问题分析:
●原链表是:1>2>3>4>5
●我们只需要把2节点指向1,3节点指向2……
●但是最重要的还是把1的next指针置为空,不然还是指向2节点,2节点也是指向1节点,就会形成环,所以我们可以先申请一个头节点为NULL,第1个节点指向NULL,然后2>1,3>2,4>3,5>4
●在循环的过程中,要把pcur指向的next指向前一个节点的指针,如果不做任何操作,就直接把next指向newhead,我们就找不到pcur的下一个节点了,所以要先保存下一个节点的指针,然后再去改变pcur的next指针。
⛷代码实现:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* newhead=NULL; ListNode* pcur=head; while(pcur) { ListNode* pnext=pcur->next; pcur->next=newhead; newhead=pcur; pcur=pnext; } return newhead; }
🏝问题2:寻找链表的中间节
【LeetCode】链接:. - 力扣(LeetCode)
⛷问题描述:
⛷问题分析:
如果我们先去遍历一下链表有多少个元素,然后把个数除以二去寻找中间节点,这样差不多要进行两次遍历,但是我们用快慢指针就能很好的避免这种情况。
⛷代码实现:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode* fast=head; ListNode* slow=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
🏝问题3:返回单链表的倒数第K个节点的值
【LeetCode】链接:. - 力扣(LeetCode)
⛷问题描述:
⛷问题分析:
这题我们也可以用快慢指针去解题,我们需要将快慢指针拉开K个节点的距离,然后我们要快慢指针同步往后走,等fast指针走到NULL,此时slow就是倒数第K个节点。
⛷代码实现:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; int kthToLast(struct ListNode* head, int k){ ListNode* fast=head; ListNode* slow=head; while(k--) { fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow->val; }
🏝问题4:合并两个有序链表
【LeetCode】链接:. - 力扣(LeetCode)
⛷问题描述:
⛷问题分析:
●创建一个头结点,然后要list1和list2区遍历,谁小就放在为节点的尾部,比如list1的节点比list2节点小,我们就可以ptail->list1,然后让list1往后面遍历,直到有一个节点为NULL,我们就跳出循环。
●后面一步我们只要把剩下链表补充到ptail的后面就可以,因为list1和list2是先后遍历,所以list1和list2不可能同时走到NULL,一定有一个先走到NULL,如果是list1先走到NULL,那么我们只要把list2剩余的节点补充到ptail的后面就可以了,即ptail->next=list1。
⛷代码实现:
/** * 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* phead=(ListNode*)malloc(sizeof(ListNode)); ListNode* ptail=phead; while(list1&&list2) { if(list1->val>list2->val) { ptail->next=list2; ptail=list2; list2=list2->next; } else { ptail->next=list1; ptail=list1; list1=list1->next; } } ptail->next=list1==NULL?list2:list1; return phead->next; }
总结:
这四个题目可以让我们对链表有一个认识,虽然很简单,但是这几个题还是很有用的,可以重点看一下,后期还会继续带来链表较难的题目,可以的铁子可以三连,感谢大家的支持。