我和我

分类

面试必刷TOP101(101) 题解(130)

/ 注册

TA的专栏 30篇文章 1人订阅

面试必刷TOP101

30篇文章 515人学习

全部文章（共232篇）

题解 | #单链表的排序#TOP12 来自专栏

思路: 1.题目是O(Nlog(n))时间负责度，当然我们第一眼可能想到，直接用辅助数组排序，然后将辅助数组辅助到链表上，可以做到数组时间O(Nlog(n)),但是数组空间O(N)，题目没说，也是可以的 2.用归并排序，自顶向下，时间复杂度O(Nlog(N))，无空间消耗，拆分后就是合并两个有序的...

Java

2022-06-26

0 327

题解 | #链表相加(二)#TOP11 来自专栏

思路: 1.两数相加肯定是先个位相加，然后进位 2.反转链表，链表头就是个位数字了，然后相加，相加后，商的值就是当前节点值，余数参数下一个节点计算进位。(因为可能最后一个节点是0，所以反转后的到的节点，如果头节点是0的话，就要去掉。看你怎么写了，因为在所有节点计算完后，余数可能为0，也可能非0，需要...

Java

2022-06-26

0 261

题解 | #两个链表的第一个公共结点#TOP10 来自专栏

思路: 差异化 a + b = b + a p1 先到达节点终点，然后将p1 放到p2的头位置，有公共节点，那说明第二次，最后都能到达最后的节点。如果有复用的，重复的节点，那必须是一样的，第一次相等的肯定是就是入环点咯 public class ListNode { int val; ...

Java

2022-06-24

0 351

题解 | #删除链表的倒数第n个节点#TOP9 来自专栏

思路: 1.首先当只有一个节点时，n=1 ，那删除后就是空节点 2.还有当n的值刚好是头节点，例如倒数第3个节点，而节点长度为3，这种就是返回head.next了 3.其他情况，我们将slow指向到要删除节点的前一个节点，那怎么才能指到呢？我们用fast节点先指向头节点，然后偏移 n - 1 个节...

Java

2022-06-24

0 515

题解 | #链表中倒数最后k个结点#TOP8 来自专栏

思路：利用快节点，先从头节点偏移 k 个位置，fast指向了第 k+1 个节点，slow指向了头节点。如果第k+1个节点是空的，那么就返回头节点否则，不断遍历循环，知道 fast指向空节点，slow就指向了倒数k个位置，因为slow -> fast 中间有k - 1 个节点 /* ...

Java

2022-06-23

0 320

题解 | #链表中环的入口结点#TOP7 来自专栏

思路：如果有环，把这个链表想象成刀，我们从刀把开始出发，刀把长x,假设第一次相遇时走了 x+y ，y是环上的距离。fast则走了2*(x+y), y % s == (2*(x+y) - x) % s ,也就是说 y%s == (x + 2y ) %s,所以x + y == s的，也就是说 slo...

Java

2022-06-23

0 233

题解 | #合并k个已排序的链表#TOP5 来自专栏

思路：自顶向下，这叫归并排序。我们要合并一定范围[start,end]的节点，拆成[start,mid], (mid,end] 两部分节点合并，将这两部分排好序的合并就ok了。然后继续拆解。 * Definition for singly-linked list. * public class...

Java

2022-06-22

0 259

题解 | #判断链表中是否有环#TOP6 来自专栏

思路：这几题都不难，思路就用文字描述吧主要就是快慢节点，如果有环，把这个链表想象成刀，我们从刀把开始出发，假设slow走了m距离，刀把长n，此时在环上相遇了，快慢指针必然会相遇，快指针肯定会超过慢指针起码一圈以上，假如环长度s。slow -> (m -n ) %s fast -> (...

Java

2022-06-22

0 280

题解 | #合并两个排序的链表#TOP4 来自专栏

思路： 1.新创建个节点，比较两个list1 和 list2 当前节点，不断遍历，将新创建的节点指向比较当中的最小的节点 2.肯定有一个节点没有遍历完，需要判断一下，直接next指向后面不为空的节点 public class ListNode { int val; ListNode ...

Java

2022-06-21

0 254

题解 | #链表中的节点每k个一组翻转#TOP3 来自专栏

思路: 1.每K个反转，这个好实现。我们新建一个节点newHead ，初始化为-1，copy 出副本进行操作headPointer，每次遍历节点，它的next指向当前节点，方便下一次遍历的时候，下一个节点可以指向它。如果刚好到k了，那我们headPointer指向当前遍历周期开始的节点。主要是为了能...

Java

2022-06-21

0 299