郑州网站建设技术精粹苏州企业服务平台

郑州网站建设技术精粹,苏州企业服务平台,有哪些网站可以做全景效果图,给厂家做代理上什么网站206. 反转链表这道题在链表界的地位#xff0c;大约等同于编程语言里的 Hello World。 虽然它是简单题#xff0c;但据我观察#xff0c;能一遍 bug free 且能清晰讲出递归逻辑的人#xff0c;其实并没有想象中那么多。很多人脑子会了#xff0c;手一写#xff0c;NPE大约等同于编程语言里的 Hello World。虽然它是简单题但据我观察能一遍 bug free且能清晰讲出递归逻辑的人其实并没有想象中那么多。很多人脑子会了手一写NPE空指针了或者链表断了。今天咱们就来彻底搞定它顺便聊聊怎么在面试里把这道题写出“花”来。题目是个啥给你一个单链表的头节点head请你反转链表并返回反转后的头节点。输入1 - 2 - 3 - 4 - 5 - NULL输出5 - 4 - 3 - 2 - 1 - NULL看着简单吧不就是把箭头调个头吗嘿链表这东西最烦人的就是由于它是单向的你一旦回头就找不到前任了一旦往前走就找不到后路了。 所以操作指针的时候得格外小心。策略一双指针迭代法这是最推荐的面试写法。逻辑清晰空间复杂度 O(1)不容易出错。核心心法三人行虽然叫双指针但其实我们需要三个变量来玩转这场“移形换影”curr当前节点我现在在哪。prev前驱节点我要把箭头指给谁我的新后继。next临时节点最重要的备胎。在我改变心意指向prev之前我得先记下来我原本要去哪不然一断链后面的节点全丢了。动图脑补流程想象一下你站在curr(比如节点 2) 的位置备份先把curr.next(节点 3) 存到next变量里。防丢失掉头把curr.next指向prev(节点 1)。关键一步链子反了挪窝prev往前走一步变成curr。curr往前走一步变成刚才备份的nextclass Solution { public ListNode reverseList(ListNode head) { // prev 初始化为 null因为反转后原本的头节点要指向 null ListNode prev null; ListNode curr head; while (curr ! null) { // 1. 记下原本的下一步去哪保存现场 ListNode nextTemp curr.next; // 2. 斩断情丝回首掏指针反转 curr.next prev; // 3. 整体向后移动 prev curr; curr nextTemp; } // 循环结束时curr 是 nullprev 才是新的头节点原本的尾巴 return prev; } }防坑指南千万别忘了最后返回的是prev不是curr循环结束时curr已经是null了。别忘了初始化prev null否则反转后的尾巴没法结束。策略二递归法如果你想在面试官面前秀一下你的抽象思维能力或者想让代码看起来短小精悍可以用递归。但说实话这玩意儿非常绕脑子不好使的时候容易把自己绕进去。核心心法甩锅递归的精髓在于信任。假设我们有一个函数 reverseList(head)它的作用是把以 head 为头的链表反转并返回新的头。面对1 - 2 - 3 - 4 - 5我节点 1想反转整个链表。我太懒了我先对 head.next也就是节点 2说“兄弟你带着后面那帮人先去反转一下。”ListNode newHead reverseList(head.next);假设第 2 步成功了现在的局面是1 - 2 - 3 - 4 - 5注意此时 1 还连着 2但 2 已经是后面那串反转后的链表的“尾巴”了。关键操作我要让 2 指回 1。head.next.next head; 翻译我下家的下家变成我自己断后路1 现在是新的尾巴了必须指向 null否则就死循环了。head.next null;class Solution { public ListNode reverseList(ListNode head) { // 递归终止条件链表为空或者只有一个节点那还反转个屁直接返回 if (head null || head.next null) { return head; } // 1. 甩锅先让后面的节点去反转 // newHead 只是为了最后返回用中间过程完全不碰它 ListNode newHead reverseList(head.next); // 2. 关键把当前节点挂到后面那串链表的尾巴上 // head.next 此时就是后面那串的尾节点 head.next.next head; // 3. 断开原来的连接防止环路 head.next null; return newHead; } }优缺点分析帅代码行数少逻辑看起来很高级。险空间复杂度是 O(N)因为要压栈。如果链表非常长可能会StackOverflow。在工程项目里还是老老实实写迭代法吧别搞这些花里胡哨的。总结反转链表这道题属于**“肌肉记忆”**级别的题目。面试求稳写迭代法双指针解释清楚prev,curr,next的作用。面试求异如果面试官问“能不能用递归”你再反手甩出第二种解法并顺便聊聊递归栈的深度问题B 格瞬间拉满。最后记住这句话操作链表前先把next存起来不然链表断了神仙也救不回来。去刷题吧祝大家都能把 offer 拿到手软