国内最专业的IT技术学习网

UI设计

当前位置:主页 > UI设计 >

一道字节跳动的算法面试题,你能做出来吗?

发布时间:2019/09/02标签:   你能    点击量:

原标题:一道字节跳动的算法面试题,你能做出来吗?
前几天有个小搭档去口试字节跳动,口试官问了他一道链表相干的算法题,不外他一时之间没做进去,就来问了我一下,感到这道题还不错,拿来说一讲。一道字节跳动的算法面试题,你能做出来吗?01 标题这实在是一道变形的链表反转题,大抵描写以下:给定一个单链表的头节点 head,完成一个调剂单链表的函数,使得每K个节点之间为一组停止逆序,而且从链表的尾部开端组起,头部残余节点数目不敷一组的不须要逆序。(不能应用行列或许栈作为帮助)比方: 链表:1->2->3->4->5->6->7->8->null, K = 3。那末 6->7->8,3->4->5,1->2列位一组。调剂后:1->2->5->4->3->8->7->6->null。此中 1,2不调剂,由于不敷一组。02 解答这道题的难点在于,是从链表的尾部开端组起的,而不是从链表的头部,假如是头部的话,那咱们仍是比拟轻易做的,由于你能够遍历链表,每遍历 k 个就拆分为一组来逆序。然而从尾部的话就纷歧样了,由于是单链表,不能今后遍历组起,不外这道题确定是用递归比拟好做。先做一道相似的反转题在做这道题之前,咱们不仿先来看看假如重新部开端组起的话,应当怎样做呢?比方:链表:1->2->3->4->5->6->7->8->null, K = 3。调剂后:3->2->1->6->5->4->7->8->null。此中 7,8不调剂,由于不敷一组。这道题咱们能够用递返来完成,假定方式reverseKNode()的功效是将单链表的每K个节点之间逆序(重新部开端组起的哦);reverse()方式的功效是将一个单链表逆序。那末关于上面的这个单链表,此中 K = 3。一道字节跳动的算法面试题,你能做出来吗?咱们把前K个节点与前面的节点宰割进去:一道字节跳动的算法面试题,你能做出来吗?temp指向的残余的链表,能够说是原成绩的一个子成绩。咱们能够挪用reverseKNode()方式将temp指向的链表每K个节点之间停止逆序。再挪用reverse()方式把head指向的那3个节点停止逆序,成果以下:一道字节跳动的算法面试题,你能做出来吗?接着,咱们只要要把这两局部给衔接起来便可以了。最初的成果以下:

版权信息Copyright © IT技术教程 版权所有    ICP备案编号:鲁ICP备09013610号