力扣-14天算法入门
第1天 二分查找
第2天 双指针
第3天 双指针
第4天 双指针
第5天 双指针
第6天 滑动窗口
第7天 广度优先搜索 / 深度优先搜索
第8天 广度优先搜索 / 深度优先搜索
第9天 广度优先搜索 / 深度优先搜索
第10天 递归 / 回溯
第11天 递归 / 回溯
第12天 动态规划
第13天 位运算
第14天 位运算
力扣-第5天 双指针
前言
本系列文章是我的力扣刷题记录,采用c++进行编写
一、876. 链表的中间结点
难度(简单)
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例1:
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
这里要注意的是由于链表无下标，我们采用vector容器去做
具体代码如下：
class Solution {
public:
ListNode* middleNode(ListNode* head) {
//头结点为head的非空单链表，要返回该链表的中间结点
//如果有两个中间结点，则返回第二个中间结点。
vector<ListNode*> a={head};
while(a.back()->next!=NULL){
a.push_back(a.back()->next);
}
return a[a.size()/2];
}
};
二、19. 删除链表的倒数第 N 个结点
难度(简单)
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例2：
输入：head = [1], n = 1
输出：[]
采用结合虚指针的快慢指针做
代码如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next=head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast !=NULL){
fast=fast->next;
}
fast = fast->next;
while (fast !=NULL)
{
fast=fast->next;
slow=slow->next;
}
slow->next = slow->next->next;
return dummyHead->next;
}
};
总结
期待大家和我交流，留言或者私信，一起学习，一起进步！