24届秋招专场·双指针巧解链表套路题

这篇具有很好参考价值的文章主要介绍了24届秋招专场·双指针巧解链表套路题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

24届秋招专场·双指针巧解链表套路题

你好,我是安然无虞。

大家好, 好久不见了, 从今天开始, 后面会经常更新笔试面试真题, 准备今年24届秋招的小伙伴可以提前看过来了哦.
24届秋招专场·双指针巧解链表套路题
咱们先从链表入手, 基础知识默认大家都会咯, 直接热题开刷, 走着…

我们知道单链表题型中有许多技巧, 其中有很多题都属于那种难者不会, 会者不难的题型, 满满的套路感, 下面整理了九道题目, 基本对应了七种技巧, 面试常考题型, 一起看看吧.

合并两个有序链表

题目链接: 合并两个有序链表
题目描述:
24届秋招专场·双指针巧解链表套路题

解题思路:

这道题就比较简单了, 属于单链表入门题型, 但是如果要让解法更简单, 最好定义一个虚拟头结点, 结果直接返回其next即可.

代码详解:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        // p1和p2均不为空时
        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
		
		// p1不为空
        if(p1)
            p->next = p1;
		// p2不为空
        if(p2)
            p->next = p2;

        return newnode->next;    
    }
};

分隔链表

题目链接: 分隔链表
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

前面一题我们是将两条有序链表合并成一条有序链表, 这一题可以将原链表分割成为两条链表.
也就是说将原链表分割成为节点值小于x的短链表和节点值不小于x的短链表即可.

注意:
如果看代码不明白的话, 最好画图去理解.

代码详解:

class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 分成节点值小于x的短链表和节点值不小于x的短链表
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        // 遍历比较原链表
        while(head != nullptr)
        {
            if(head->val < x)
            {
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2 = p2->next;
            }

            head = head->next;
        }

        // 将节点值不小于x的短链表的尾置空
        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};

合并K个有序链表

题目链接:合并K个有序链表
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

前面有讲到合并两个有序链表, 其实合并K个有序链表和它的解题思想很类似, 但是为了能够快速获取K个链表的最小节点, 我们需要定义一个最小堆, 将K个链表的头结点插入其中, 这样一来, 每次就可以获取K个节点的最小节点.

代码解析:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点, 将所有节点尾插其后
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义一个最小堆, 将K个链表的头结点插入其中
        // 用到了C++中新语法, 不熟悉的小伙伴可以去查阅哦
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head != nullptr)
                pq.push(head);
        }

        while(!pq.empty())
        {
            // 获取堆顶节点, 即当前最小节点, 尾插到新链表后
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            // 
            if(pMin->next != nullptr)
                pq.push(pMin->next);

            p = p->next;
        }

        return newnode->next;
    }
};

链表中倒数最后K个节点

题目链接: 链表中倒数最后K个节点
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

本题是想找到链表的最后K个节点, 前提是要找到倒数第K个节点, 如何在一次遍历的情况下找到呢?
首先定义两个指针p1和p2, 均指向链表的头结点. 一开始让p1先走k步(此时如果p1再走n-k步就走到链表的尾了), 这个时候p2从头和p1一起走, 直到p1指向nullptr为止, 此时p2在第n-k+1个节点上, 即倒数第k个位置, 大家可以画图去理解, 这里我就不画了哈哈哈哈.

代码详解:

class Solution {
public:

    ListNode* FindKthToTail(ListNode* pHead, int k) 
    {
        // write code here
        ListNode* p1 = pHead, *p2 = pHead;

        if(pHead == nullptr)
            return nullptr;

        // p1先走k步
        for(int i = 0; i < k; i++)
        {
            // 注意判断防止越界导致段错误
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        // p2从头开始和p1一起走, 直至p1指向nullptr时, p2所在位置即为倒数第k个位置
        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};

变形题: 删除链表的倒数第N个节点

题目链接: 删除链表的倒数第N个节点
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

单链表中删除某一个节点, 前提是要先找到该节点的前一个节点, 同时为了防止头删第一个节点, 我们还需要定义一个虚拟头结点, 将head节点尾插其后.

代码解析:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义一个虚拟头结点 - 注意单链表对虚拟头结点的运用
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 防止头删第一个节点

        // 单链表中删除某一个节点, 前提需要找到它前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);
        
        prev->next = prev->next->next;

        return newnode->next;
    }

    // 单链表中找倒数第K个节点
    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针p1和p2, p1先走k步(再走n-k步到尾), 然后p2从头开始h和p1一起走
        // 直到p1指向空, 此时p2在第n-k+1个节点的位置, 即倒数第k个节点
        ListNode* p1 = head, *p2 = head;

        if(head == nullptr)
            return nullptr;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};

链表的中点

题目链接: 链表的中点
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

利用快慢指针, 快指针一次走两步, 慢指针一次走一步, 当快指针指向末尾时, 慢指针所在的位置即是链表的中点.

代码详解:

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针一次走两步, 慢指针一次走一步
        // 当快指针指向末尾时, 慢指针即是中点
        // 画图更好理解
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

判断链表是否有环

题目链接: 判断链表是否有环
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

利用快慢指针, 很简单不说了

代码详解:

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针一次走两步, 慢指针一次走一步
        // 当快指针指向末尾时, 慢指针即是中点
        // 画图更好理解
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

环形链表II

题目链接: 环形链表II
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

下面是我两年前画的图…大家可以参考

24届秋招专场·双指针巧解链表套路题
代码解析:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 判断链表是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        // 循环非break退出, 说明没环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 否则有环, slow从头重新开始走
        // 二者再次相遇即为入口点
        slow = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

相交链表

题目链接: 相交链表
题目描述:
24届秋招专场·双指针巧解链表套路题
解题思路:

这题的解题思路就比较有意思了, 本题是求相交链表的交点, 难点在于什么, 就像上图一样, 链表A和链表B的长度很大可能不一样, 这样我们就做不到一次循环可以找到二者的交点, 那如何解决该难点呢?
我们可以定义两个指针p1和p2, 其中p1指向链表A, p2指向链表B. 一开始p1先遍历链表A然后再遍历链表B, 同理p2先遍历链表B再遍历链表A, 这样就可以保证二者遍历长度相同, 能够同时走到相交点.

代码分析:文章来源地址https://www.toymoban.com/news/detail-484224.html

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针, p1指向链表A, p2指向链表B
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        // 为了让p1和p2遍历链表的长度一样, 采用下面的做法
        while(p1 != p2)
        {
            // p1遍历完链表A, 开始遍历链表B
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            // p2遍历完链表B, 开始遍历链表A
            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        // 交点返回即可 - 画图去理解
        return p1;
    }
};

种一棵树最好的时间是十年前, 其次是现在.
一起加油, 我们很快就会再见.

到了这里,关于24届秋招专场·双指针巧解链表套路题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023届秋招图像算法岗面经记录(TPlink(普联)、潮州三环、中电十所、科大讯飞、旷视、超参数、虹软、大华、速腾聚创、中兴、哲库、字节、OPPO、百度、之江实验室、蚂蚁、Intel、小米)

    秋招战线拉的很长,四个月过去,offer二三,皆不甚满意。然世间没有完满之事,大多数情况下都是在几个次优解之间做选择。且选择越多后悔越多,人最重要的可能还是知足。现总结自身情况与经验教训,给有幸点开的小伙伴一点点参考。 【 自身背景】: 四川某末流985,

    2024年02月10日
    浏览(89)
  • 24秋招,帆软测试开发工程师一面

    大家好,我是chowley,今天来回顾一下,我当时参加帆软测试开发工程师的技术面试 时间:55min 平台:腾讯会议 自我介绍 实习经历 为啥选择测试岗 实习中的主要收获是什么? 印象比较深的bug?权限相关 收到需求之后,你是怎么做拆解的?测试计划-测试用例-进行测试 测试

    2024年01月20日
    浏览(43)
  • 24秋招,百度测试开发工程师三面

    大家好,我是chowley,今天来回顾一下,我当时参加百度秋招补录,测试开发工程师的第三面-leader面 到面试开始的时间,面试官打电话表示让我等十分钟,随后跳过自我介绍,直接开面 时间:50min 平台:如流 为什么参加补录 先手撕,我看看面评 手撕:读取文件内容,将出现

    2024年01月19日
    浏览(42)
  • 算法:数组常见套路1---双指针、取模、打擂台法

    1、题目: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对

    2024年02月09日
    浏览(37)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • 剑指 Offer 24. 反转链表

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月06日
    浏览(40)
  • LeetCode算法小抄 -- 链表(快慢指针、双指针、回文链表)

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计10077字,阅读大概需要10分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ Collection 子接口之 Queue (LeetCode上经常用,手撕算法题!

    2023年04月08日
    浏览(38)
  • C++入门【24-C++ 传递指针给函数】

    C++ 允许您传递指针给函数,只需要简单地声明函数参数为指针类型即可。 下面的实例中,我们传递一个无符号的 long 型指针给函数,并在函数内改变这个值: 实例 当上面的代码被编译和执行时,它会产生下列结果: Number of seconds :1294450468 能接受指针作为参数的函数,也能

    2024年01月25日
    浏览(35)
  • 24. 两两交换链表中的节点

    2024年02月07日
    浏览(45)
  • LeetCode24.两两交换链表中的节点

    力扣题目链接

    2024年01月20日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包