Leetcode 学习—GitHub
①简单 ②中等 ③困难以后不再维护此篇文章,后续的题解都上传到:陶攀峰的 LeetCode 题解
链表
相交链表(160)①
2020-07-14 15:45:48
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
注意点:是节点相同,而不是val相同
1)、解决方案
1 | /** |
2)、思路
A:a + c + null + b
B:b + c + null + a
当A走完(a+c+null+b)的时候,B也走完了(b+c+null+a),此时他们指向的节点就是相同的。
3)、问题
当时我想的改为
1 | a = a.next == null ? headB : a.next; |
这种在不存在相交的时候会存在问题,不会返回null。
反转链表(206)①
2020-07-14 16:19:45
https://leetcode-cn.com/problems/reverse-linked-list/description/
1)、解决方案
1 | /** |
2)、思路
1 | 0. 用一个指针来遍历原链表、新链表原本为空 |
合并两个有序链表(21)①
2020-07-14 16:27:49
https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
1)、解决方案
1 | /** |
2)、思路
new一个节点,用于拼接合并后的链表。
任何一个都不为空,进行比较,进行链接,并指向下一个节点。
其中一个为空,直接拼接另外一个。
删除排序链表中的重复元素(83)①
2020-07-14 17:14:54
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/description/
1)、解决方案
1 | /** |
2)、思路
头节点不变,用一个指针来遍历链表
如果val相同就断开,不同就指向下一个节点。
链表中倒数第k个节点(剑指 Offer 22)①
2020-07-15 11:02:29
https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
1)、解决方案
1 | /** |
2)、思路
一张图明示(采用双指针方式,fast先走k步,再一起走,直到fast为null时返回slow)
链表的中间结点(876)①
2020-07-15 13:28:01
https://leetcode-cn.com/problems/middle-of-the-linked-list/
1)、解决方案
1 | /** |
2)、思路
采用双指针:fast一次走两步,slow一次走一步。
当fast走到头了,slow就是返回中间节点。
回文链表(234)①
1)、解决方案
1 | /** |
2)、思路
双指针同步走,slow走过的节点用于反转。
fast走到头,若fast!=null,说明,节点总数是奇数,slow在中间,应该往后再走一步。
此时,进行前半段(翻转链表)与后半段(slow链表)进行同步走比较。
删除链表中的节点(237)①
2020-07-15 14:34:49
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/submissions/
1)、解决方案
1 | /** |
2)、思路
一开始没看懂题目,还在想着为什么不给head,然后就去看题解了。
才知道,值改变一下,断开连接就行了。主要是改变值。
移除链表元素(203)①
2020-07-15 15:01:20
https://leetcode-cn.com/problems/remove-linked-list-elements/
1)、解决方案
- 哑节点(推荐)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);// 哑节点,dummy.next指向头节点
dummy.next = head;
ListNode prev = dummy, curr = head;
while (curr != null) {
if (curr.val == val) {
prev.next = curr.next;// 删除节点
} else {
prev = curr;
}
curr = curr.next;
}
return dummy.next;// 返回头节点
}
} - 空节点,删除时需要判断是不是头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode prev = null, curr = head;
while (curr != null) {
if (curr.val == val) {
if (prev == null) head = head.next;// 删除头节点
else prev.next = curr.next;// 删除非头节点
} else {
prev = curr;
}
curr = curr.next;
}
return head;// 返回头节点
}
}
2)、思路
、采用哑节点,双指针方式同步走,找到要删除的节点,就用断开(prev.next = curr.next;)
、如果非哑节点,需要判断删除的是不是头节点,若是头节点,把头节点指向下一个节点即可(head = head.next;)
环形链表(141)①
2020-07-15 15:52:26
https://leetcode-cn.com/problems/linked-list-cycle/
1)、解决方案
1 | /** |
2)、思路
想象一些环形跑道,一个人跑的快,一个人跑的慢。他们俩一直跑,终究会相遇。
、fast先行一步
、不相遇就一直跑
、相遇了,说明有环
、fast跑到头了,无环
二进制链表转整数(1290)①
2020-07-15 15:52:42
https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer/
1)、解决方案
1 | /** |
2)、思路
进行位移操作。具体为什么?暂时说不出来。
注意:位运算要加括号
删除链表的倒数第N个节点(19)②
2020-07-15 08:48:50
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
1)、解决方案
1 | /** |
2)、思路
1 | 采用快慢指针的方式: |
两两交换链表中的节点(24)②
2020-07-15 10:41:17
https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/
1)、解决方案
1 | /** |
2)、思路
想画图解来着,实在太麻烦了,就没画。
、三个变量:start,end用来交换,prev在交换前指向start的前一个节点。
、如果prev为null,就是第一次交换,改变了头节点,把头节点指向修改后的头节点。
、如果prev不为null,表示非第一次交换,也就是没有改变头节点,prev.next交换前指向start,交换后应该指向end。
、把prev指向下一个start前一个节点,把start指向下一个要交换的start节点。
两数相加(2)②
2020-07-27 11:46:24
https://leetcode-cn.com/problems/add-two-numbers/
1)、解决方案
1 | /** |
2)、思路
强调:其实运算逻辑和我们摆竖式计算是一个道理。
旋转链表(61)②
2020-07-28 08:44:45
https://leetcode-cn.com/problems/rotate-list/
1)、解决方案
1 | /** |
1 | // 这个是我之前想到的一版,快慢指针。 |
2)、思路
、遍历计算总元素数
、计算翻转次数
、找到新的头节点的上一个节点,也就是结果是尾节点
附上快慢指针的思路图,如果知道了count数,可以不使用快慢指针法。
删除排序链表中的重复元素 II(82)②
2020-07-28 18:13:14
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
1)、解决方案
1 | /** |
2)、思路
、创建一个哑节点dummy,用于链接不重复的元素,dummy.next用于return使用。
、采用双指针:开始,结束。都从head开始遍历,end走到不等于start时终止。
、若start.next==end,也就是start与end长度为1(是相邻节点),把start进行链接。
分隔链表(86)②
2020-07-29 15:56:48
https://leetcode-cn.com/problems/partition-list/
1)、解决方案
1 | /** |
2)、思路
参考:力扣官方解法
两个链接用于拼接<x 与 >=x,最后两个链表再链接
反转链表 II(92)②
2020-07-30 09:03:45
https://leetcode-cn.com/problems/reverse-linked-list-ii/
1)、解决方案
1 | /** |
2)、思路
、定义哑节点dummy,dummy.next用于return。
、初始化p(pointer指针),循环走到m节点。定位一个节点g(guard守卫),位置一直是m-1节点。
、翻转所需循环次数:n-m
、采用头插法。记作remove=p.next,把remove断开,插入g后面(g.next=remove)。
有序链表转换二叉搜索树(109)②
2020-08-01 21:43:37
https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
1)、解决方案:两种
》》》创建一个新的方式
1 | /** |
》》》递归,单个方法解决
2020-08-27 10:43:58
1 | /** |
2)、思路
、快慢指针找中点。
、找到中点之后,把中点当做root节点。
、再以中点把链表分为左右两段,再以左右两段再分别进行快慢指针查找。
不会的话,可以根据代码来参考图片。
我画的简陋流程图。可以看出标出的数字 1~11 就是第几次进入 helper方法,我用紫色分割线来表示递归深度。
》》》方式2的画图
复制带随机指针的链表(138)②
2020-08-05 10:47:01
https://leetcode-cn.com/problems/copy-list-with-random-pointer/
1)、解决方案
1 | /* |
2)、思路
参考:1. 拼接,创建节点设置val 2. 改变random 3. 断开,改变next
环形链表 II(142)②
2020-08-12 10:12:13
https://leetcode-cn.com/problems/linked-list-cycle-ii/
1)、解决方案
1 | /** |
2)、思路
1 | 从head 到 入口点有a个,环上有b个。 |
重排链表(143)②
2020-08-13 10:12:35
https://leetcode-cn.com/problems/reorder-list/
1)、解决方案
1 | /** |
》》》可以优化
1 | ListNode fast = head.next, slow = head; |
2)、思路
分四步走:
1 | 1. 找到中间节点,进行分割链表:前半部分(one),后半部分(two) |
对链表进行插入排序(147)②
2020-08-14 11:02:12
https://leetcode-cn.com/problems/insertion-sort-list/
1)、解决方案
1 | /** |
2)、思路
、定义一个 tail 节点,指向已排序的尾节点
、依次对 tail.next 进行排序
、如果 tail 与 tail.next 已经是正确顺序,就进行下一次循环(tail = tail.next)
、如果 tail 与 tail.next 未进行正确顺序,定义一个 prev 节点,把 tail.next 断开,再插入到 prev 的后面,在插入前要从头开始遍历找到 prev 的位置,这个位置要保证顺序的稳定
排序链表(148)②
2020-08-14 16:45:56
https://leetcode-cn.com/problems/sort-list/
1)、解决方案
1 | /** |
2)、思路
看图,对着代码理解。
如果递归很晕的话,可以画图,就使用两个元素进行画图,再依次增多,方便理解。
奇偶链表(328)②
2020-08-14 17:46:38
https://leetcode-cn.com/problems/odd-even-linked-list/
1)、解决方案
1 | /** |
2)、思路
节点数 < 3 ,直接 return head
用一个布尔变量标识是否为奇节点
oddTail 指向已经排好的奇节点链表尾部
tail 指向已经排好的链表尾部,此时,tail.next 就是要进行链接的节点
可能上面我表达不是很清楚,下面来看图。
官方一句话:解决链表问题最好的办法是在脑中或者纸上把链表画出来。
扁平化多级双向链表(430)②
2020-08-25 10:06:19
https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/
1)、解决方案
1 | /* |
2)、思路
、一开始我也想着是用递归,但是发现,贼麻烦耶!递着递着,我都不知道龟跑哪儿了。于是,我用了迭代的思路。
、cur 当前遍历的节点,这时候,遍历要分两个情况:有孩子,无孩子
》》》有孩子:取到孩子节点(newNext = cur.child 把 cur 与 newNext 连接),取到孩子链表的尾节点 tail(把 tail 与 oldNext 连接)
》》》无孩子:遍历下一个节点(cur = cur.next)
可以优化(我就不做了):
、不存在孩子节点:cur = cur.next
、存在孩子节点:
》》》孩子链表上无孩子节点(无 cur 孙子节点),把 cur 指向 oldNext
》》》孩子链表中存在孩子节点(有 cur 孙子节点),就把 cur 指向 第一个孙子节点
两数相加 II(445)②
2020-08-14 19:32:26
https://leetcode-cn.com/problems/add-two-numbers-ii/
1)、解决方案:两种
》》》方法1、旋转,再相加
1 | /** |
》》》方法2、栈
1 | /** |
2)、思路
把 l1 ,l2 翻转,再相加。
注意:相加后的链表要进行头插,如果进行尾插的话,还要相加后的链表进行一次翻转。
》》》如果你想进阶:不破坏链表结构的话,可以使用栈数据结构。
》》》递归的话,暂时我做不出来。
个人不太倾向于用 Java 中的 Object 来对算法的实现。
设计链表(707)②
2020-08-15 13:16:45
https://leetcode-cn.com/problems/design-linked-list/
1)、解决方案
1 | class MyLinkedList { |
2)、思路
之前看过 LinkedList 源码,这里我只使用了 next,并没有使用 prev
分隔链表(725)②
2020-08-16 11:00:20
https://leetcode-cn.com/problems/split-linked-list-in-parts/
1)、解决方案
1 | /** |
2)、思路
、分割链表,首先要对 root 分割 k 份
、每一份的节点数的差不能超过 1,首先要计算每一份的平均长度 avg = count / k ,其中 count 是 root 链表的总节点数
、计算前几份的节点数要 + 1,mod = count % k,也就是前 mod 份的节点数是 avg + 1,其他的都是 avg
、后面就是循环 k 次,依次给数组赋值,都在代码里了,这就不做解释了,这个不用画图也很好理解
链表组件(817)②
2020-08-16 12:00:13
https://leetcode-cn.com/problems/linked-list-components/
1)、解决方案
1 | /** |
2)、思路
、要遍历链表,那是肯定的,依次判断当前节点是否存在在数组中。
、重点:如果想连续的节点都存在数组中,也只能 + 1,所以,你要定义一个标志位 isExistsPrev,来判断是否连续(上一个节点是否存在)
、分析情况,只能存在三种:
》》》情况一、当前节点不存在,count 不变,isExistsPrev = false; 表示当前节点不存在
》》》情况二、当前节点存在,当上一个节点不存在,count + 1,isExistsPrev = true; 表示当前节点存在
》》》情况三、当前节点存在,当上一个节点存在,此时 count 不变,isExistsPrev 也不变(仍为 true),表示当前节点存在
可能上述,我写的很啰嗦,看代码吧,代码来说话。
关于我用时击败
用时的人少,是因为节点是否存在数组,这时候判断每次都要进行遍历。
这里可以用 Set 集合进行优化,Set 集合的特性,不重复,并且使用 Hash 定位,很少发生 Hash 碰撞的话,查找速度比遍历数组快多了
二叉树中的列表(1367)②
2020-08-17 19:48:34
https://leetcode-cn.com/problems/linked-list-in-binary-tree/
1)、解决方案
1 | /** |
2)、思路
- 先用 head 与 根 进行比较,比较如果相等,就拿链表的下一个节点 与 树的左右节点进行比较,递归。。
- 若 head 与 根 比较是 false,那么就把根的 左右节点 当做根,再进行递归。。
- 对着下面的图,来进行分析。
可能你听我上面说的,或者看代码很迷,你画个图,或者 造个假数据,debug 走一下,你就懂了。
没有人天生就很牛逼,一步一步来。无他,熟尔。
从链表中删去总和值为零的连续节点(1171)②
2020-08-18 10:31:03
https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
1)、解决方案:三种
》》》方法1、遍历再求和
1 | /** |
》》》方法2、map存取
太绝了。
1 | /** |
》》》方法3、递归
简单粗暴,画图方便理解。
递归的理解,要从一个节点,两个节点,依次尝试递归,找到规律。
1 | /** |
2)、思路
》》》方法1、
、定义一个哑节点,dummy.next 用于 return
、定义 guard(守卫节点),用于断开
、cur(cursor 指针),用于遍历求和 sum
情况一、当 sum == 0,断开(guard.next = cur.next)
情况二、当 sum != 0,继续往后走(cur = cur.next)
情况三、当 cur 走完,也没找到 sum != 0,更换守卫节点(guard = guard.next)
》》》方法2、方法3、不要问,为什么? 对着代码看图,去理解。
链表中的下一个更大节点(1019)②
2020-08-19 10:10:32
https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
1)、解决方案
1 | /** |
》》》优化。ArrayList 使用
1 | public int[] nextLargerNodes(ListNode head) { |
2)、思路
第一次遍历链表,确认数组长度。
第二次遍历链表,依次给数组赋值。
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路
xxxx()①
<>
1)、解决方案
1 |
2)、思路