力扣-第5天 双指针

力扣-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 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?

力扣-第5天 双指针

示例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;
    }
};

总结

期待大家和我交流,留言或者私信,一起学习,一起进步!

上一篇:【力扣LeetCode】环形链表


下一篇:【剑指offer】链表中倒数第k个节点