昨天文章:《龙年红包封面的领取步骤,目前每个账号只能领取一个》。
在网上查了一下腾讯今年的校招薪资,这里主要以技术类为主,比如后端,前端,算法等。基本上都是20k以上,最高的看到有一个29k的,并且都是16薪,还有各种补贴,全部算下来总包基本上能达到40w以上,对于一个刚毕业的学生来说还是很不错的。
看完了腾讯今年的校招薪资,我们再来看一道关于腾讯的面试题。因为腾讯人比较多,所以面试题也是比较多,我们今天就顺便挑一道来看下。这题是LeetCode的第24题:两两交换链表中的节点。这题实际上不算难,但一网友在腾讯面试的时候遇到这题却没写出来,这题除了腾讯以外,其他公司也考过,可以看下。
问题描述
来源:LeetCode第24题
难度:中等
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
问题分析
这题要求的是两两交换相邻的链表节点,但不能通过修改节点的值来完成。对于链表这类题最好的学习方法就是在一张纸上把他的解决思路一步一步的画出来,这样就会看的更加明白。
对于这道题来说,我们可以使用迭代的方式,也可以使用递归的方式来解决。迭代的方式这里就不在介绍,我们来看一下递归的解决方式。
首先来说如果节点为空或者只有一个节点是没法交换的,所以能交换的前提是至少要有两个节点,所以一个链表我们可以把它分成3份,分别是第1个节点,第2个节点和后面的所有节点。后面的所有节点我们可以使用递归的方式,如下图所示:
JAVA:
public ListNode swapPairs(ListNode head) {// 边界条件判断if (head == null || head.next == null)return head;// 从第3个节点往后使用递归方式进行交换ListNode third = swapPairs(head.next.next);// 从第3个节点往后都交换完了,我们只需要交换前两个节点即可,// 这里我们把链表分为3组,分别是第1个节点,第2个节点,后面// 的所有节点,也就是1→2→3All,我们要把它变为2→1→3AllListNode second = head.next;head.next = third;second.next = head;return second;
}
C++:
public:ListNode* swapPairs(ListNode* head) {// 边界条件判断if (head == nullptr || head->next == nullptr)return head;// 从第3个节点往后使用递归方式进行交换ListNode* third = swapPairs(head->next->next);// 从第3个节点往后都交换完了,我们只需要交换前两个节点即可,// 这里我们把链表分为3组,分别是第1个节点,第2个节点,后面// 的所有节点,也就是1→2→3All,我们要把它变为2→1→3AllListNode* second = head->next;head->next = third;second->next = head;return second;}
-------------------------end-------------------------
笔者简介
博哥,真名:王一博,毕业十多年,《算法秘籍》作者,专注于数据结构和算法的讲解,在全球30多个算法网站中累计做题2000多道,在公众号中写算法题解700多题,对算法题有自己独特的解题思路和解题技巧,喜欢的可以给个关注,也可以下载我整理的1000多页的PDF算法文档。
耗时两年终于出版了!
龙年红包封面来了,可以领取了。
最近两个月,我公众号阅读从一千多增长到三四万,这样写才会出现爆款,才能被官方推荐。
字节面试原题,两人都没做出来,都凉了
网友:华为一面原题,看到题就笑了,结果面完10分钟不到就给挂了。