失眠网,内容丰富有趣,生活中的好帮手!
失眠网 > 来 做一道字节跳动面试的简单算法题

来 做一道字节跳动面试的简单算法题

时间:2024-05-03 00:11:11

相关推荐

来 做一道字节跳动面试的简单算法题

面试大厂,算法基本是必面的,特别是字节跳动,技术面最后一个问题就是算法题,这次给大家带来一道字节跳动面试出的一道简单算法题。

请听题:

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。并返回合并后的链表表头。

难度:简单

示例1:

输入:1->2->4, 1->3->4输出:1->1->2->3->4->4

限制:

0 <= 链表长度 <= 1000

请完成代码编写:

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode mergeTwoLists(ListNode head1, ListNode head2) {//to do this}

题目是这么个题目,看着不难,确实也不难的,只是如果没怎么接触过算法这一块,或者没怎么接触过链表的使用,其实一时还是不知道怎么入手比较好,大家可以看到这里,别往下看,先思考一下,看是否有思路,尝试自己写一下,看20分钟是否能比较好的完成这道题,做出来是一回事,既然是算法,还要关注它的时间复杂度和空间复杂度哦~

那实际上,稍微分析一下题目就很容易想到一种思路,两个链表都是递增的,要求合并它们,合并之后仍然是递增有序的,那我们可以逐个拿第二个链表的元素和第一个链表的元素去比较,找到一个合适的位置,插入到第一个链表中去,最后合并的链表就是第一个链表,然后再想办法找到第一个链表的表头返回即可。

话是这么说,但是实际写代码的时候,如果完全不引入变量的话,你会发现不是那么好处理,其实上面那个思路咱们可以稍微转换一下,那就是如果我有第三个链表head,然后我分别拿第一个链表head1的val和第二个链表head2的val比较,如果head1.val<head2.val,我就把head1放入到head里面去,然后再拿head1的下一个元素next的val去和刚刚的head2.val去比较,依然看谁大谁小,把小的放入head的下一个元素next中去,一直这样进行下去,知道head1或者head2遍历完成,剩下还没遍历完的就直接挂到head那个链表上去就好了。

好,大体思路相信大家都理解了,可以自己尝试一下。接下来咱们把思路步骤列出来并具体的代码给实现出来。

题目要求返回合并之后的表头,我们需要定义好一个虚拟表头head,因为如果不定义好,最后排完序我们的链表指针到尾部去了;定义当前节点cur,初始化指向虚拟表头;开始遍历head1和head2,循环条件是head1!=null && head2!=null;比较head1.val和head2.val,哪个小,就把哪个元素赋值给cur.next,并把小的链表那个指针下移,当前节点也下移剩余元素处理,最后看head1和head2那个链表还有剩余元素,因为它们不会同时遍历完,要么head1先遍历完,要么head2先遍历完,把没有遍历完的挂到cur的下一个元素即可,因为本身是有序的。返回链表头节点,因为第一个节点是我们自己虚拟的,head.next才是我们合并完成之后的头节点。

看下面这个图更好理解:

代码实现

public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}class Solution {public ListNode mergeTwoLists(ListNode head1, ListNode head2) {//to do this//1、定义好一个虚拟节点,初始值可设置为0ListNode head = new ListNode(0);//2、定义一个链表来放head1和head1的元素,初始值就等于headListNode cur = head;//3、遍历head1和head2while(head1!=null && head2!=null){//4、比较head1.val和head2.val,哪个小,就把哪个元素赋值给cur.next,并把小的链表那个指针下移if(head1.val<=head2.val){cur.next = head1;head1 = head1.next;}else{cur.next = head2;head2 = head2.next;}//当前节点也下移cur = cur.next;}//5、剩余元素处理cur.next = head1==null ? head2:head1;//6、返回链表头节点return head.next; }//测试一下public static void main(String[] args){//构建两个链表ListNode l1 = new ListNode(1);l1.next = new ListNode(2);l1.next.next = new ListNode(4);ListNode l2 = new ListNode(1);l2.next = new ListNode(3);l2.next.next = new ListNode(4);ListNode head = new Solution().mergeTwoLists(l1,l2);StringBuilder sb = new StringBuilder();while(head!=null){sb.append(head.val);head = head.next;if(head!=null){sb.append("->");}}System.out.println(sb.toString());}}

输出结果:

1->1->2->3->4->4

复杂度分析: 时间复杂度 O(M+N):M,N 分别为链表的长度,合并操作需遍历两链表。 空间复杂度O(1) : 节点引用 head , cur使用常数大小的额外空间。

所有总体效果还是不错的,至少时间复杂度不是O(N^2),是一个线性阶,也只额外引入一个节点引用。

你做出来了吗?可能大家都做出来了,或许比我这个实现更好~

如果觉得《来 做一道字节跳动面试的简单算法题》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。