LeetCode刷题(已废弃)

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
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;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;

ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}

2)、思路
在这里插入图片描述
A:a + c + null + b
B:b + c + null + a
当A走完(a+c+null+b)的时候,B也走完了(b+c+null+a),此时他们指向的节点就是相同的。

3)、问题
当时我想的改为

1
2
a = a.next == null ? headB : a.next;
b = b.next == null ? headA : b.next;

这种在不存在相交的时候会存在问题,不会返回null。

反转链表(206)①

2020-07-14 16:19:45
https://leetcode-cn.com/problems/reverse-linked-list/description/

1)、解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = null;// return 节点
ListNode curr = head;// 用于遍历原链表

while (curr != null) {
ListNode temp = curr.next;// 获取下一个
curr.next = newHead;// 连成新链
newHead = curr;// 指向新链
curr = temp;// 当前指针指向下一个
}
return newHead;
}
}

2)、思路
在这里插入图片描述

1
2
3
4
5
0. 用一个指针来遍历原链表、新链表原本为空

1. 当前遍历的节点指向新链表
2. 把新链表头指向当前遍历节点
3. 再把当前遍历节点指向下一个节点

合并两个有序链表(21)①

2020-07-14 16:27:49
https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

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
26
27
28
29
30
31
32
33
34
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
// dummy用于连接合并后的链表
// curr用于遍历两个链表
ListNode dummy = new ListNode(0), curr = dummy;

// 任何一个链表遍历完就结束
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;// 记得当前节点指向下一个
}

// 其中一个遍历完,直接连上另外一个
curr.next = l1 == null ? l2 : l1;

// 返回新合并后的链表
return dummy.next;
}
}

2)、思路
在这里插入图片描述
new一个节点,用于拼接合并后的链表。
任何一个都不为空,进行比较,进行链接,并指向下一个节点。
其中一个为空,直接拼接另外一个。

删除排序链表中的重复元素(83)①

2020-07-14 17:14:54
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/description/

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
26
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head)
{
// 用于遍历链表
ListNode curr = head;

while (curr != null && curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;// == 断开链表
} else {
curr = curr.next;// != 指向下一个节点
}
}

// 返回头节点
return head;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// 条件不符合,返回空
if (head == null || k < 1) {
return null;
}

// fast先走k步
ListNode fast = head;
while (k-- > 0) {
fast = fast.next;
}

// 查找的是头节点,直接返回
if (fast == null) {
return head;
}

// 查找的不是头节点,双指针同步走
ListNode slow = head;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}

// 返回要查找的节点
return slow;
}
}

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
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 middleNode(ListNode head) {
// 双指针
ListNode fast = head, slow = head;

// 同步走,fast走到头为止
while (fast != null && fast.next != null) {
fast = fast.next.next;// 一次走2步
slow = slow.next;// 一次走1步
}

// 返回slow指针
return slow;
}
}

2)、思路
采用双指针:fast一次走两步,slow一次走一步。
当fast走到头了,slow就是返回中间节点。
在这里插入图片描述

回文链表(234)①

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// fast,slow:快慢指针
// reverse:把链表前半段反转,reverse指向反转后的头
// temp:用于指向移动前的slow节点
ListNode fast = head, slow = head, reverse = null, temp;

// 两节点同步走,slow走后的节点进行翻转
while (fast != null && fast.next != null) {

// 指向走之前的slow
temp = slow;

// fast走2步,slow走1步
fast = fast.next.next;
slow = slow.next;

//连接
temp.next = reverse;
reverse = temp;
}

// 链表节点数:
// 奇数,slow指向中间那个
// 偶数,slow指向中间那两个的后一个
// fast != null:表示链表节点数是奇数,所以slow要指向它的下一个节点
if (fast != null) {
slow = slow.next;
}

// reverse VS slow
while (reverse != null) {
// 不相等,直接退出
if (reverse.val != slow.val) {
return false;
}
// 往后走
reverse = reverse.next;
slow = slow.next;
}

return true;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}

2)、思路
一开始没看懂题目,还在想着为什么不给head,然后就去看题解了。
才知道,值改变一下,断开连接就行了。主要是改变值。
在这里插入图片描述

移除链表元素(203)①

2020-07-15 15:01:20
https://leetcode-cn.com/problems/remove-linked-list-elements/

1)、解决方案

  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;// 返回头节点
    }
    }
  2. 空节点,删除时需要判断是不是头节点
    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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// 不符合
if (head == null || head.next == null) {
return false;
}

// fast先行一步
ListNode fast = head.next, slow = head;

// 不相遇就一直跑
while (fast != null && fast.next != null) {
if (fast == slow) return true;// 相遇了,说明有环
fast = fast.next.next;// fast走2步
slow = slow.next;// slow走1步
}

return false;// fast跑到头了,无环
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int getDecimalValue(ListNode head) {
int num = 0;
while (head != null) {
num = (num << 1) + head.val;//等同于 num = num * 2 + head.val;
head = head.next;
}
return num;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;

// fast指针往后走n步
while (n-- > 0) {
fast = fast.next;
}

// 删除的是头节点
if (fast == null) return head.next;

// 删除的非头节点
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}

// 断开节点
slow.next = slow.next.next;

// 返回头部
return head;
}
}

2)、思路
在这里插入图片描述

1
2
3
4
5
6
7
采用快慢指针的方式:

快指针先往后走n步。
如果走到了空,说明删除的是头节点,此时就返回头节点的next节点。
快慢指针再一起走。
让慢指针定位到要删除节点的上一个节点。
断开连接,返回头节点。

两两交换链表中的节点(24)②

2020-07-15 10:41:17
https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/

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
26
27
28
29
30
31
32
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
/**
* start,end是需要交换的值.
* prev就表示start的前一个节点,默认为null,因为头节点没有上一个节点
*/
ListNode prev = null, start = head, end;

while (start != null && (end = start.next) != null) {
start.next = end.next;
end.next = start;

if (prev == null) {
head = end;// 头节点改变
} else {
prev.next = end;// 头节点不变
}
prev = start;
start = start.next;
}

return head;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;

while (l1 != null || l2 != null || carry == 1) {
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;

int sum = v1 + v2 + carry;

carry = sum / 10;

curr.next = new ListNode(sum % 10);
curr = curr.next;

if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}

return dummy.next;
}
}

2)、思路
强调:其实运算逻辑和我们摆竖式计算是一个道理。
在这里插入图片描述

旋转链表(61)②

2020-07-28 08:44:45
https://leetcode-cn.com/problems/rotate-list/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {

// 直接返回
if (head == null || head.next == null || k == 0) return head;

// 计算节点个数。循环结束,curr指向尾节点
ListNode curr = head;
int count = 1;
while (curr.next != null) {
count++;
curr = curr.next;
}

// 计算翻转次数
k = k % count;

// 无需翻转
if (k == 0) return head;

// 首尾连接成环
curr.next = head;

// curr走count-k步,指向倒数第 k+1 个节点
for (int i = 0; i < count - k; i++) {
curr = curr.next;
}

// 指向新的头节点
head = curr.next;
// curr作为尾节点
curr.next = null;

return head;
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 这个是我之前想到的一版,快慢指针。
// 后来发现,我已经计算了count数了,就不需要快慢指针了。
public ListNode rotateRight(ListNode head, int k) {

// 直接返回
if (head == null || head.next == null || k == 0) return head;

// 计算节点个数
ListNode curr = head;
int count = 0;
while (curr != null) {
count++;
curr = curr.next;
}

// 计算翻转次数
k = k % count;

// 无需翻转
if (k == 0) return head;

// 采用快慢指针
ListNode fast = head, slow = head;
// fast 先走k步,fast指向第k+1个节点
while (k-- > 0) {
fast = fast.next;
}

// fast slow 一起走,fast指向尾节点时,slow指向倒数第k+1个节点
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}

// 尾节点与头节点连接
fast.next = head;
// 指向新的头节点
head = slow.next;
// slow作为尾节点
slow.next = null;

return head;
}

2)、思路
、遍历计算总元素数
、计算翻转次数
、找到新的头节点的上一个节点,也就是结果是尾节点

附上快慢指针的思路图,如果知道了count数,可以不使用快慢指针法。
在这里插入图片描述

删除排序链表中的重复元素 II(82)②

2020-07-28 18:13:14
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {

// 直接返回
if (head == null || head.next == null) return head;

// 定义一个哑节点,dummy.next 用于 return 使用
ListNode dummy = new ListNode(0);

// 用于动态链接不重复的节点
ListNode curr = dummy;

/*
start 开始位置
end 结束位置
*/
for (ListNode start = head, end = head; start != null; start = end) {
// end往后走,直到为null,或!=start.val
while (end != null && start.val == end.val) end = end.next;
// 若长度为1,则进行尾插
if (start.next == end) {
curr.next = start;
curr = curr.next;
}
}

// 尾部设为null,否则可能携带其他节点
curr.next = null;

// 返回结果
return dummy.next;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public static ListNode partition(ListNode head, int x) {

// 直接返回
if (head == null || head.next == null) return head;

// 左 <
ListNode dummyLeft = new ListNode(0), left = dummyLeft;
// 右 >=
ListNode dummyRight = new ListNode(0), right = dummyRight;

// 遍历 head
for (; head != null; head = head.next) {
if (head.val < x) {
left.next = head;
left = left.next;
} else {
right.next = head;
right = right.next;
}
}

// 链接。注意:最后要清空尾部
left.next = dummyRight.next;
right.next = null;

return dummyLeft.next;
}
}

2)、思路
参考:力扣官方解法
两个链接用于拼接<x 与 >=x,最后两个链表再链接

反转链表 II(92)②

2020-07-30 09:03:45
https://leetcode-cn.com/problems/reverse-linked-list-ii/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {

// 定义哑节点,dummy.next 用于 return
ListNode dummy = new ListNode(0);
dummy.next = head;


/*
g:guard 守卫 (一直指向 m节点的前一个节点)
p:pointer 指针 (用于遍历 [m,n] 节点)
*/
ListNode g = dummy, p = head;

// 循环走完,g 指向 m节点的前一个节点,p 指向 m节点
for (int i = 1; i < m; i++) {
g = g.next;
p = p.next;
}

// 反转部分,循环 n-m次
for (int i = 0; i < n - m; i++) {
// 要断开的节点
ListNode remove = p.next;

// 断开
p.next = remove.next;

// 头插。注意:下面两行代码顺序不能反
remove.next = g.next;
g.next = remove;
}

return dummy.next;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
// 调用递归,并返回
return helper(head, null);
}

private TreeNode helper(ListNode head, ListNode tail) {
// 递归退出条件
if (head == tail) return null;

// 快慢指针找中点。fast走到头,slow就是中点
ListNode fast = head, slow = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}

// 定义根节点
TreeNode root = new TreeNode(slow.val);

// 找左右节点。以及左右节点的左右节点。。。递归
root.left = helper(head, slow);
root.right = helper(slow.next, tail);

// 返回
return root;
}
}

》》》递归,单个方法解决
2020-08-27 10:43:58

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {

/*
1. 特殊情况处理
、为空,返回 null
、只有一个节点,直接返回该节点
*/

if (head == null) return null;
if (head.next == null) return new TreeNode(head.val);

/*
2. 快慢指针找中点
、fast走到头,slow就是中点(偶数时为右节点)
、prev 是 slow 前一个节点,用于把链表一分为二(断开)
*/
ListNode fast = head, slow = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

// 3. 断开
prev.next = null;

// 4. 定义根节点
TreeNode root = new TreeNode(slow.val);

/*
5. 设置左右节点(递归)
、左链表放左边,因为值都比 root 小
、右链表放右边,因为值都比 root 大
*/
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);

// 6. 返回
return root;
}
}

2)、思路
、快慢指针找中点。
、找到中点之后,把中点当做root节点。
、再以中点把链表分为左右两段,再以左右两段再分别进行快慢指针查找。

不会的话,可以根据代码来参考图片。
我画的简陋流程图。可以看出标出的数字 1~11 就是第几次进入 helper方法,我用紫色分割线来表示递归深度。
有序链表转换二叉搜索树(109)②

》》》方式2的画图
在这里插入图片描述

复制带随机指针的链表(138)②

2020-08-05 10:47:01
https://leetcode-cn.com/problems/copy-list-with-random-pointer/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;

public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/

class Solution {
public Node copyRandomList(Node head) {
// 不符合,直接 return
if (head == null) return null;


// 1. val -> 每个原节点后面创建一个新节点
// A -> B -> C
// A -> A' -> B -> B' -> C -> C'
for (Node cursor = head; cursor != null; cursor = cursor.next.next) {
Node newNode = new Node(cursor.val);

newNode.next = cursor.next;
cursor.next = newNode;
}

// 2. random -> 设置新节点的随机节点
for (Node cursor = head; cursor != null; cursor = cursor.next.next) {
cursor.next.random = (cursor.random != null) ? cursor.random.next : null;
}


// 3. next -> 将两个链表分离
Node newHead = head.next;
Node oldCursor = head;// A -> B -> C
Node newCursor = head.next;// A' -> B' -> C'
while (oldCursor != null) {
oldCursor.next = oldCursor.next.next;
newCursor.next = (oldCursor.next != null) ? newCursor.next.next : null;

oldCursor = oldCursor.next;
newCursor = newCursor.next;
}

// return
return newHead;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// 1. 不符合直接返回
if (head == null) return head;

// 2. 找到第一次相遇的节点
ListNode meetNode = meet(head, head);

// 3. 无环
if (meetNode == null) return null;

// 4. 有环 -> 再走 a 步,进行第二次相遇,找到环入口节点
ListNode fast = head, slow = meetNode;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}

/**
* 快慢指针一起走<br/>
* >>>如果有环,快指针会跟慢指针相遇,返回相遇节点<br/>
* >>>如果无环,返回null
*
* @param fast 快指针:每次走两步
* @param slow 慢指针:每次走一步
* @return 返回第一次相遇的节点,不相遇返回 null
* @author 陶攀峰
* @date 2020-08-12 09:31
*/
private ListNode meet(ListNode fast, ListNode slow) {
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 1. 第一次相遇
if (fast == slow) return slow;
}

// 2. 无环
return null;
}
}

2)、思路
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
从head 到 入口点有a个,环上有b个。

# 无环
fast = null || fast.next = null

# 有环 -> 进行第二次相遇,找到入口点
fast 路程 = f
slow 路程 = s
fast 速度是 slow 的二倍 -> f = 2s
fast 比 slow 多走了 n 个环的长度 -> f = s + nb
由上可得:s = nb,因此 slow 再走 a 步就可到达环的入口点
把 fast 指向头节点(fast = head),fast 到环的入口点也是 a 步
此时,fast 和 slow 一起走,相等的地方就是头节点。

重排链表(143)②

2020-08-13 10:12:35
https://leetcode-cn.com/problems/reorder-list/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public static void reorderList(ListNode head) {
// 不符合,直接返回
if (head == null || head.next == null) return;

/*
快慢指针,找到中点
fast:每次走 2 步
slow:每次走 1 步。(分割链表的后半部分的头节点)
slowPrev:每次走 1 步,始终是 slow 的前一个节点。(也是分割链表前半部分的尾节点)

节点总数:
偶数,slow 指向中间两个的后一个
奇数,slow 指向中间一个

因此,
节点总数为偶数 前半部分长度 = 后半部分长度
节点总数为奇数 前半部分长度 + 1 = 后半部分长度
*/
ListNode slowPrev = new ListNode(0);
slowPrev.next = head;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
slowPrev = slowPrev.next;
}

// 前后两部分断开,链表一分为二
slowPrev.next = null;

// 翻转后半部分链表
ListNode g = new ListNode(0);
g.next = slow;
while (slow.next != null) {
ListNode remove = slow.next;
slow.next = remove.next;
remove.next = g.next;
g.next = remove;
}

// one:前半部分 头节点
// two:后半部分 头节点
ListNode one = head;
ListNode two = g.next;

// 两个链表依次拼接,注意代码的顺序(已踩坑)
ListNode curr = new ListNode(0);
while (one != null) {
curr.next = one;
one = one.next;
curr = curr.next;

curr.next = two;
two = two.next;
curr = curr.next;
}

// 前半部分走完,再链接上后半部分
curr.next = two;

// 注意:在上面链接的时候,head 还是指向重排后链表的头节点
}
}

》》》可以优化

1
2
3
4
5
6
7
8
9
10
11
12
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}

初始化时,fast 先走一步,这样为奇数时,依然指向中间节点。
但为偶数时,就指向中间两个的左节点了。

这样使 slow.next = null; 就可以直接断开了。

无需再多一个 slowPrev 节点来进行断开。

2)、思路
分四步走:

1
2
3
4
1. 找到中间节点,进行分割链表:前半部分(one),后半部分(two)
2. 前部部分尾节点 与 后半部分头节点断开
3. 旋转后半部分(two)链表
4. 进行 one,two 两个链表依次拼接

对链表进行插入排序(147)②

2020-08-14 11:02:12
https://leetcode-cn.com/problems/insertion-sort-list/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
// 1. 不符合,直接返回
if (head == null || head.next == null) return head;

// 2. 定义一个哑节点,dummy.next 用于 return
ListNode dummy = new ListNode(0);
dummy.next = head;

/*
3. 遍历,进行排序
tail:已排序链表的尾节点
tail.next:要进行排序的节点
*/
for (ListNode tail = head; tail.next != null; ) {
// 情况一、已经正确排序,遍历下一个要排序的节点
if (tail.val <= tail.next.val) {
tail = tail.next;
continue;
}

/*
情况二、未正确排序。下面分三步走

步骤 1、找到要插入位置的前一个节点 prev
注意:是 <= ,如果是 < 就不稳定了
什么是稳定?:val 相同的节点,顺序依然不变
*/
ListNode prev = dummy;
while (prev.next.val <= tail.next.val) prev = prev.next;

// 步骤 2、断开
ListNode remove = tail.next;
tail.next = tail.next.next;

// 步骤 3、插入
remove.next = prev.next;
prev.next = remove;
}

// 4. return
return dummy.next;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// 1. 不符合,直接 return。也是递归的结束条件。
if (head == null || head.next == null) return head;

/*
2. 快慢指针,找到中点
fast:每次走两步(初始化先走一步,是为了节点数为偶数时,slow可以指向中间两个节点的左节点)
slow:每次走一步(指向左链表的尾节点)
two:右链表的头节点
节点数
奇数:slow 指向中间节点
偶数:slow 指向中间两节点的左节点
*/
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}

ListNode two = slow.next;

// 3. 断开。链表一分为二
slow.next = null;


/*
4. 左右递归
left 指向 head 排序后的头节点
right 指向 two 排序后的头节点
*/
ListNode left = sortList(head);
ListNode right = sortList(two);

// 5. 链接
ListNode dummy = new ListNode(0), curr = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}

// 6. 注意:其中一个链接完成,要链接另一个
curr.next = (left != null) ? left : right;

// 7. return
return dummy.next;
}
}

2)、思路
看图,对着代码理解。
如果递归很晕的话,可以画图,就使用两个元素进行画图,再依次增多,方便理解。
在这里插入图片描述

奇偶链表(328)②

2020-08-14 17:46:38
https://leetcode-cn.com/problems/odd-even-linked-list/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
// 不用排序,直接 return
if (head == null || head.next == null || head.next.next == null) return head;

/*
oddTail:已排好奇链表的尾部
tail:已排好链表的尾部
*/
ListNode oddTail = head;
ListNode tail = head.next;

/*
isOdd:判断是否是奇数节点
*/
for (boolean isOdd = true; tail.next != null; isOdd = !isOdd) {
if (isOdd) {
// 奇数

// 1. 断开
ListNode remove = tail.next;
tail.next = tail.next.next;
// 2. 链接
remove.next = oddTail.next;
oddTail.next = remove;
// 3. 奇数尾部改变
oddTail = oddTail.next;
} else {
// 偶数。继续遍历下一个
tail = tail.next;
}
}

// return 头节点
return head;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/

class Solution {
public Node flatten(Node head) {

//////////////
///遍历节点///
//////////////
for (Node cur = head; cur != null; cur = cur.next) {
// 情况一、有孩子
if (cur.child != null) {
// 1. 拿到 next 节点
Node oldNext = cur.next;

// 2. 把孩子 child 当做新的 next 节点
Node newNext = cur.child;
cur.next = newNext;
newNext.prev = cur;
cur.child = null;// 记得设为 null(断开)

// 3. 找到尾节点 tail,把 tail 与原 next 节点连接
Node tail = newNext;
while (tail.next != null) tail = tail.next;
tail.next = oldNext;
if (oldNext != null) oldNext.prev = tail;
}

// 情况二、无孩子,直接遍历下一个节点
}

return head;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 1. 其中一个为空,直接 return 另一个
if (l1 == null) return l2;
if (l2 == null) return l1;

// 2. 翻转链表
l1 = rev(l1);
l2 = rev(l2);

/*
3.
head:用于执行相加后链表的头节点
carry:进位,默认 0
*/
ListNode head = null;
int carry = 0;


/*
4. 循环相加。
注意条件:任何一个链表没走完,或有进位,就创建节点
*/
while (l1 != null || l2 != null || carry != 0) {
// 4.1 对节点取值
int v1 = (l1 == null) ? 0 : l1.val;
int v2 = (l2 == null) ? 0 : l2.val;

// 4.2 相加
int sum = v1 + v2 + carry;

// 4.3 计算进位
carry = sum / 10;

// 4.4 新建节点,进行头插
ListNode newNode = new ListNode(sum % 10);
newNode.next = head;
head = newNode;

// 4.5 指向下一个节点
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}

// 5. return
return head;
}


/**
* 传入一个链表,进行翻转,返回翻转后的头节点
*
* @param head 要进行翻转的链表
* @return head 翻转后的链表
* @author 陶攀峰
* @date 2020-08-14 18:15
*/
public static ListNode rev(ListNode head) {
// 1. 不符合,直接 return
if (head == null || head.next == null) return head;

// 2. 定义一个哑节点,dummy.next 用于 return
ListNode dummy = new ListNode(0);
dummy.next = head;

// 3. 循环翻转 n -1 次
while (head.next != null) {
// 3.1 断开
ListNode remove = head.next;
head.next = remove.next;
// 3.2 插入
remove.next = dummy.next;
dummy.next = remove;
}

// 4. return
return dummy.next;
}
}

》》》方法2、栈

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 1. 其中一个为空,直接 return 另一个
if (l1 == null) return l2;
if (l2 == null) return l1;

// 2. 创建栈,并添加数据
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
for (; l1 != null; l1 = l1.next) s1.push(l1.val);
for (; l2 != null; l2 = l2.next) s2.push(l2.val);
/*
3.
head:用于执行相加后链表的头节点
carry:进位,默认 0
*/
ListNode head = null;
int carry = 0;
/*
4. 循环相加。
注意条件:任何一个链表没走完,或有进位,就创建节点
*/
while (!s1.empty() || !s2.empty() || carry != 0) {
// 4.1 对栈取值
int v1 = s1.empty() ? 0 : s1.pop();
int v2 = s2.empty() ? 0 : s2.pop();

// 4.2 相加
int sum = v1 + v2 + carry;

// 4.3 计算进位
carry = sum / 10;

// 4.4 新建节点,进行头插
ListNode newNode = new ListNode(sum % 10);
newNode.next = head;
head = newNode;
}

// 5. return
return head;
}
}

2)、思路
把 l1 ,l2 翻转,再相加。
注意:相加后的链表要进行头插,如果进行尾插的话,还要相加后的链表进行一次翻转。

》》》如果你想进阶:不破坏链表结构的话,可以使用栈数据结构。

》》》递归的话,暂时我做不出来。

个人不太倾向于用 Java 中的 Object 来对算法的实现。

设计链表(707)②

2020-08-15 13:16:45
https://leetcode-cn.com/problems/design-linked-list/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
     class MyLinkedList {
Node head;
Node tail;
int size;

class Node {
Node next;
int val;

Node() {
}

Node(int val) {
this.val = val;
}
}

/**
* Initialize your data structure here.
*/
public MyLinkedList() {

}

/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
*/
public int get(int index) {
// 不符合
if (index < 0 || index >= size) return -1;

// 找到节点,return
Node cur = head;
// index-- > 0 :走 index 步
// --index > 0 :走 index-1 步
while (index-- > 0) cur = cur.next;
return cur.val;
}

/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
*/
public void addAtHead(int val) {
Node newNode = new Node(val);

newNode.next = head;
head = newNode;

if (tail == null) tail = newNode;

++size;
}

/**
* Append a node of value val to the last element of the linked list.
*/
public void addAtTail(int val) {
Node newNode = new Node(val);
if (tail != null) {
tail.next = newNode;
tail = newNode;
} else {
// head tail 都指向 newNode
head = tail = newNode;
}

++size;
}

/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
if (index > size) {
// 1. 不插
return;
} else if (index <= 0) {
// 2. 头插
addAtHead(val);
} else if (index == size) {
// 3. 尾插
addAtTail(val);
} else {
// 4. 找到插入位置的前一个节点,进行插入
Node cur = head;
while (--index > 0) cur = cur.next;
Node newNode = new Node(val);
newNode.next = cur.next;
cur.next = newNode;
++size;
}
}

/**
* Delete the index-th node in the linked list, if the index is valid.
*/
public void deleteAtIndex(int index) {
if (index < 0 || size == 0 || index >= size) {
// 1. 不删
return;
} else if (size == 1) {
head = tail = null;
} else if (index == 0) {
// 2. 删头
head = head.next;
} else {
// 3. 删其他节点
Node cur = head;
while (--index > 0) cur = cur.next;
// 4. 删尾
if (cur.next == tail) tail = cur;
cur.next = cur.next.next;
}

--size;
}

}

/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/

2)、思路
之前看过 LinkedList 源码,这里我只使用了 next,并没有使用 prev

分隔链表(725)②

2020-08-16 11:00:20
https://leetcode-cn.com/problems/split-linked-list-in-parts/

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
// 1. 初始化数组
ListNode[] listNode = new ListNode[k];

// 2. 计算总节点数 count
int count = 0;
for (ListNode cur = root; cur != null; cur = cur.next) {
count++;
}

/*
3. 平均每段至少有几个节点
例如:10 / 3 = 3,平均每段有 3 个节点
*/
int avg = count / k;

/*
4. 前几段应该 + 1
例如:10 % 3 =1,第一段的节点数应该 + 1
*/
int mod = count % k;

// 5. 循环 k 次,给数组依次赋值
for (int i = 0; i < k; i++) {
// 5.1 当前段,实际的长度
int len = (i < mod) ? avg + 1 : avg;

ListNode cur = root;
// 5.2 走 len - 1 步。如果 root != null, cur 指向被截取的尾节点
while (--len > 0) {
if (cur == null) break;
cur = cur.next;
}

ListNode newRoot = null;
// 5.3 newRoot 先指向分割后的右半部分 头节点,再进行断开
if (cur != null) {
newRoot = cur.next;
cur.next = null;
}
// 5.4 赋值,再重新指向分割后的右半部分的头节点
listNode[i] = root;
root = newRoot;
}

// 6. return
return listNode;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] G) {
// 1. 上一个节点是否存在。头节点没有上一个节点,所以默认 false
boolean isExistsPrev = false;

// 2. 计算组件的数量,用于 return
int count = 0;

// 3. 遍历链表,计算组件数量 count
for (ListNode cur = head; cur != null; cur = cur.next) {

// 3.1 当前节点存在
if (isExists(cur.val, G)) {
/*
当前节点存在,上一个节点存在,才能 count + 1
并修改当前节点标志位位 true,用于下一个节点做判断,即使下一个节点也存在,也不会 count + 1
*/
if (isExistsPrev == false) {
++count;
isExistsPrev = true;
}
continue;
}

// 3.2 当前节点不存在
isExistsPrev = false;

}

// 4. return
return count;
}

/**
* 判断一个数组 ns 中是否含有元素 n
*
* @param n 一个 int 值
* @param ns 含有 int 值的数组
* @return true:存在 false:不存在
* @author 陶攀峰
* @date 2020-08-16 11:38
*/
public boolean isExists(int n, int[] ns) {
// 1. 遍历,存在就 return true
for (int value : ns) {
if (value == n) return true;
}
// 2. 遍历完成,找不到存在的,返回 false
return false;
}
}

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
// 为空肯定不行,不能进行 val 比较了
if (root == null) return false;

/*
1. 判断 head 是否为 root 的一部分
2. 当 1 false 时,就拿 head 与 root 的左节点进行比较
3. 当 1,2 都为 false 时,就拿 head 与 root 的右节点进行比较
*/
// 判断 当前节点,如果不对,再看 左子树 和 右子树 >>> 若左右子树都不对,就看左右子树的左右子树
return find(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}

/**
* 判断 head 是否为 root 的一部分
*
* @param head 链表头节点
* @param root 树的根节点
* @author 陶攀峰
* @date 2020-08-17 19:32
*/
public boolean find(ListNode head, TreeNode root) {
// 链表走完,返回 true
if (head == null) return true;
// head 还有值,树走完了,肯定不行,返回 false
if (root == null) return false;
// 值不相同,返回 false
if (head.val != root.val) return false;
// 值相同,让 链表下个节点 与 左右节点进行比较
return find(head.next, root.left) || find(head.next, root.right);
}
}

2)、思路

  1. 先用 head 与 根 进行比较,比较如果相等,就拿链表的下一个节点 与 树的左右节点进行比较,递归。。
  2. 若 head 与 根 比较是 false,那么就把根的 左右节点 当做根,再进行递归。。
  3. 对着下面的图,来进行分析。
    在这里插入图片描述

可能你听我上面说的,或者看代码很迷,你画个图,或者 造个假数据,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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {

// 1. 不符合,直接返回
if (head == null) return head;

// 2. 定义哑节点,dummy.next 用于 return
ListNode dummy = new ListNode(0);
dummy.next = head;

// 3. guard(守卫):cur 初始位置的前置节点,用于(sum == 0 时,断开)
ListNode guard = dummy;

// 4. 循环,查看是否有和为 0 的区间,有则断开
outer:
while (guard.next != null) {

/*
cur(cursor 指针):从 guard.next 开始,依次往后遍历求和
sum:计算 cur 走过节点的 val 和

情况一、sum == 0,直接断开
注意:断开后,【跳到外部】进行下一次循环,guard 指针不变
情况二、sum != 0,继续往后走
*/
int sum = 0;
for (ListNode cur = guard.next; cur != null; cur = cur.next) {
if ((sum += cur.val) == 0) {
guard.next = cur.next;
continue outer;
}
}

// 情况三、找不到 sum == 0 的区间,继续从下一个节点开始找(更换守卫)
guard = guard.next;
}

// 5. return
return dummy.next;
}
}

》》》方法2、map存取
太绝了。

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
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {

// 1. 定义哑节点,dummy.next 用于 return
ListNode dummy = new ListNode(0);
dummy.next = head;

// 2. 定义 Map,用于保存
Map<Integer, ListNode> map = new HashMap<>();

// 3. 若同一和出现多次会覆盖,即记录该sum出现的最后一次节点
int sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
map.put(sum, d);
}

// 4. 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
d.next = map.get(sum).next;
}

// 5. return
return dummy.next;
}
}

》》》方法3、递归
简单粗暴,画图方便理解。
递归的理解,要从一个节点,两个节点,依次尝试递归,找到规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
if (head == null) return null;

int sum = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
// 求和 sum == 0 ,间接删除 head~cur 之间的节点
if ((sum += cur.val) == 0) return removeZeroSumSublists(cur.next);
}

// 从 head 开始遍历,没有 sum == 0 的情况,递归执行 head.next
head.next = removeZeroSumSublists(head.next);

return head;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
// 1. 计算数组长度,并创建数组
int len = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
len++;
}
int[] nums = new int[len];

// 2. 遍历所有节点,依次给 数组赋值
int i = 0;
for (ListNode guard = head; guard != null; guard = guard.next) {
/*
2.1 cur 从 guard.next 开始往后走。
如果有大于的,就进行赋值,否则不赋值,默认 0
*/
for (ListNode cur = guard.next; cur != null; cur = cur.next) {
if (cur.val > guard.val) {
nums[i] = cur.val;
break;
}
}
// 2.2 记得,在 guard 走一步的时候,下标 i 也要走一步
i++;
}

// 3. return
return nums;
}
}

》》》优化。ArrayList 使用

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
public int[] nextLargerNodes(ListNode head) {
// 1. 初始化 List
List<Integer> list = new ArrayList<>();

// 2. 遍历所有节点,依次给 数组赋值

for (ListNode guard = head; guard != null; guard = guard.next) {
/*
2.1 cur 从 guard.next 开始往后走。
如果有大于的,就进行赋值,否则不赋值,默认 0
*/
int num = 0;
for (ListNode cur = guard.next; cur != null; cur = cur.next) {
if (cur.val > guard.val) {
num = cur.val;
break;
}
}
// 2.2 添加数据
list.add(num);
}

// 3. return 集合 -> 数组
return list.stream().mapToInt(Integer::intValue).toArray();
}

2)、思路
第一次遍历链表,确认数组长度。
第二次遍历链表,依次给数组赋值。

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路

xxxx()①

<>

1)、解决方案

1
2


2)、思路