快手2023秋招一面真题解析

文章预览

来自公众号：吴师兄学算法前言今天分享的是快手 C++ 一面算法真题解析。合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。题目解析和代码这道题目实际上就是归并排序的一个降维版本。首先，我们设定一个虚拟节点 dummy，把两个链表的节点都一个个连接到 dummy 上来。设置一个指针 pre，一开始指向虚拟节点 dummy，这个指针始终指向已经合并成功之后链表的尾节点，所以一开始在虚拟节点 dummy上。接下来，反复的执行如下的判断，直到 l1 或者 l2 指向了 null 。1、如果 l1 当前节点的值小于等于 l2 ，把 l1 当前的节点接在 pre 节点的后面，同时将 l1 指针往后移一位。2、如果 l1 当前节点的值大于 l2 ，把 l2 当前的节点接在 pre 节点的后面，同时将 l2 指针往后移一位。3、由于 ………………………………