LCR 140. 训练计划 IIhttps://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
给定一个头节点为 head
的链表用于记录一系列核心肌群训练项目编号,请查找并返回倒数第 cnt
个训练项目编号。
思路:双指针,快指针先走cnt步然后快慢指针同时向前走,当快指针为空时慢指针所在位置即为倒是第cnt个编号
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode *fast=head,*slow=head;
for(int i=1;i<=cnt;i++)
fast=fast->next;
while(fast)
{
fast=fast->next;
slow =slow->next;
}
return slow;
}
};
141. 环形链表https://leetcode.cn/problems/linked-list-cycle/
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true
。 否则,返回 false
。
思路:双指针,一个快指针一个慢指针,快指针每次走两步(有风险:快指针可能为空要特殊处理一下)慢指针走一步。如果两个指针能相遇则有环,如果不能相遇则没有环
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast=head,*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return 1;
}
return false;
}
};
26. 删除有序数组中的重复项https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
考虑 nums
的唯一元素的数量为 k
,你需要做以下事情确保你的题解可以被通过:
- 更改数组
nums
,使nums
的前k
个元素包含唯一元素,并按照它们最初在nums
中出现的顺序排列。nums
的其余元素与nums
的大小不重要。 - 返回
k
。
思想:双指针,快指针如果与慢指针相等快指针++,当快指针不等于慢指针时,慢指针++快慢赋值给慢指针,然后快指针++。直到快指针遍历完数组结束。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast=1,slow=0;
if(nums.size()==1)
return 1;
while(fast<nums.size())
{
if(nums[fast]==nums[slow])
fast++;
else
{
slow++;
nums[slow]=nums[fast];
fast++;
}
}
return slow+1;
}
};
53. 最大子数组和https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。
思路:将数组和与最大和比较,如果数组和大于最大和则更新,否则最大和加下一位数组元素判断有没有当前最大和大。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max=INT_MIN;
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
if(sum>max)max=sum;
if(sum<0)sum=0;
}
return max;
}
};
876. 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/
给你单链表的头结点 head
,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
思路:快指针走两步慢指针走一步
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast=head,*slow =head;
while(fast&& fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
};
21. 合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:当头节点和中间节点的处理方式不同时手动添加一个虚头节点,
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//创建虚头节点
ListNode* Head = new ListNode();
ListNode* Tail = Head;
while(l1 && l2)
{
if(l1->val<=l2->val)
{
Tail->next=l1;
l1=l1->next;
}
else
{
Tail->next=l2;
l2=l2->next;
}
Tail=Tail->next;
}
//判断剩余
if(l1) Tail->next=l1;
if(l2) Tail->next=l2;
return Head->next;
}
};
文章来源地址https://www.toymoban.com/news/detail-837575.html文章来源:https://www.toymoban.com/news/detail-837575.html
到了这里,关于链表习题-力扣oj (附加思路版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!