快手2023秋招一面真题解析

文章预览

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