Boom LeetCode入门(四)链表

常用链表结构

基本的链表结构,例如单向链表、双向链表的使用较为常见,不再介绍

而对于几种集合结构:HashSet、HashMap以及TreeMap

其中HashSet和HashMap均为无序集合,HashSet中仅存储Key信息,而HashMap中则以Key-Value键值对的方式存储。TreeMap同样存储键值对信息,但是对键按照有序进行存储,因而,对于TreeMap中传入的键信息为对象时,应当传入对应的比较器以便于排序,否则会报错

对于链表的回顾主要关注于以下一些常见算法题

反转链表

反转单向链表

反转单向链表-leetcode

反转单向链表-牛客

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 reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = head;
ListNode pre = null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
// return recu(head, null);
}

// public ListNode recu(ListNode cur, ListNode pre){
// if(cur == null) return pre;
// ListNode res = recu(cur.next, cur);
// cur.next = pre;
// return res;
// }
}

反转双向链表

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
package p4.list;

public class ReverseDouList {
static class Node{
int val;
Node next;
Node pre;
Node(int val){
this.val = val;
}
}

public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
node1.pre = null;
node2.pre = node1;
node3.pre = node2;
node4.pre = node3;
node5.pre = node4;
Node head = reverse(node1);
while(head != null){
System.out.println(head.val);
head = head.next;
}
Node tail = node1;
while(tail != null){
System.out.println(tail.val);
tail = tail.pre;
}
}

private static Node reverse(Node head) {
if(head == null){
return head;
}
Node prev = null;
Node cur = head;
while(cur != null){
Node temp = cur.next;
cur.next = prev;
cur.pre = temp;
prev = cur;
cur = temp;
}
return prev;
}
}

打印有序链表公共部分

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
package p4.list;

public class PrintCommonPart {
class Node{
int val;
Node next;
Node(int val){
this.val = val;
}
}
public void printCommonPart(Node l1, Node l2){
if(l1 == null || l2 == null){
return;
}
while(l1 != null && l2 != null){
if(l1.val == l2.val){
System.out.println(l1.val);
l1 = l1.next;
l2 = l2.next;
}else if(l1.val < l2.val){
l1 = l1.next;
}else{
l2 = l2.next;
}
}
}
}

判断链表回文结构

BM13 判断一个链表是否为回文结构

对于如何判断回文结构,追求时间复杂度时,利用栈实现。第一次遍历将所有数入栈,第二次遍历,边遍历边出栈比对

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
import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/

public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head == null || head.next == null) return true;
Stack<Integer> stack = new Stack<>();
ListNode cur = head;
while(cur != null){
stack.push(cur.val);
cur = cur.next;
}
cur = head;
while(cur != null){
if(cur.val == stack.pop()){
cur = cur.next;
}else{
break;
}
}
return stack.isEmpty();
}
}

而在追求空间复杂度时,利用快慢指针找到链表中间节点,反转后半部分链表进行比对,这样不用另外开辟栈空间即可完成回文结构的判断

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
import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/

public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head == null || head.next == null) return true;
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode pre = head;
ListNode tail = reverse(slow);
while(pre != tail && pre != null && tail != null){
if(pre.val != tail.val){
return false;
}
pre = pre.next;
tail = tail.next;
}
return true;
}

public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}

链表值划分

链表值的划分可以看作是快速排序的某一阶段在链表中的实现,具体实现流程是,在遍历过程中以6个指针记录大于x的头结点、大于x的尾节点、等于x的头节点、等于x的尾节点、小于x的头结点、小于x的尾部节点

一次遍历完成后,将大于x的尾节点指向等于x的头节点,等于x的尾节点指向大于x的头结点 完成值的划分,需要留意的是在拼接过程中可能存在头尾节点为空的情况,需要逐一判断

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
package p4.list;

import com.sun.jndi.toolkit.ctx.HeadTail;

/**
* @author:sliu
* @data 2022/5/11 9:43
*/

public class Code03_SplitList {
static class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
ListNode node1 = new ListNode(2);
ListNode node2 = new ListNode(1);
ListNode node3 = new ListNode(2);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(3);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
ListNode head = splitList(node1,3);
while(head != null){
System.out.println(head.val);
head = head.next;
}
}

public static ListNode splitList(ListNode head, int num){
if(head == null || head.next == null){
return head;
}
//6个ListNode分别记录,小于、等于、大于num的左右边界
ListNode minHead = null;
ListNode minTail = null;
ListNode equalHead = null;
ListNode equalTail = null;
ListNode maxHead = null;
ListNode maxTail = null;
ListNode cur = head;
ListNode temp = null;
while(cur != null){
if(cur.val == num){
if(equalHead == null){
equalHead = cur;
equalTail = cur;
}
temp = cur.next;
equalTail.next = cur;
equalTail = cur;
cur = temp;
}else if(cur.val < num){
if(minHead == null){
minHead = cur;
minTail = cur;
}
temp = cur.next;
minTail.next = cur;
minTail = cur;
cur = temp;
}else{
if(maxHead == null){
maxHead = cur;
maxTail = cur;
}
temp = cur.next;
maxTail.next = cur;
maxTail = cur;
cur = temp;
}
}
minTail.next = null;
equalTail.next = null;
maxTail.next = null;
if(minHead == null){
if(equalHead == null){
return maxHead;
}else{
if(maxHead != null){
equalHead.next = maxHead;
}
return equalHead;
}
}else{
if(equalHead == null){
if(maxHead != null){
minTail.next = maxHead;
}
return minHead;
}else{
minTail.next = equalHead;
if(maxHead != null){
equalTail.next = maxHead;
}
return minHead;
}
}
}
}

复制含有随机指针节点的链表

复杂链表复制

借用map结构存储所有的拷贝节点,例如遍历时,将node1节点拷贝node1'并将其存入map中{node1, node1'}这样,遍历一次后,所有节点都在map中有对应的拷贝项,再次遍历原数组,对于原数组中的next和random指针,从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
import java.util.*;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode cur = pHead;
while (cur != null) {
map.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
cur = pHead;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(pHead);
}
}

该方法中借助HashMap完成拷贝,因而所使用的空间较大,空间复杂度大,如何降低空间的使用呢

核心思想是一致的,保存每一个节点的拷贝项到该节点的映射关系,是解决该问题的关键

不使用HashMap保持映射关系,那么可以通过node1→node1‘→node2→node2'→........链表形式进行映射,映射完成后修改链表节点next指针完成最终拷贝

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
import java.util.*;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cur = pHead;
RandomListNode head = pHead.next;
while(cur != null){
RandomListNode temp = new RandomListNode(cur.label);
temp.next = cur.next;
cur.next = temp;
cur = temp.next;
}
cur = pHead;
head = pHead.next;
RandomListNode res = pHead.next;
while(cur != null){
res.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
if(res.next != null){
res = res.next.next;
}
}
cur = pHead;
res = pHead.next;
while(cur != null){
cur.next = cur.next.next;
cur = cur.next;
if(res.next != null){
res.next = res.next.next;
res = res.next;
}
}
return head;
}
}

单链表相交

要解决该问题,首先要判断所给出的两个链表是否有环,有无环以及哪一个链表有环,不同情形下求相交节点的方式不同

因此,首先要解决的问题就是如何判断链表是否有环

判断链表是否有环

环形链表

(1)借助HashSet

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.
* 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;
HashSet<ListNode> set = new HashSet<>();
while(head!=null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}

(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
/**
* 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;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}

环的入口

当链表有环时,还需要拿到环的入口,才能返回两个链表的交点

剑指 Offer II 022. 链表中环的入口节点

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
/**
* 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) {
if(head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
slow = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}

链表相交节点

okok,解决以上两个小问题后, 打怪升级终于来到了最终问题:找到相交节点

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
/**
* 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 == headB) return headA;
if(headA == null || headB == null || headA.next == null || headB.next == null) return null;
ListNode cycleA = detectCycle(headA);
ListNode cycleB = detectCycle(headB);
if(cycleA == null && cycleB == null){
int len = 0;
ListNode endA = headA;
ListNode endB = headB;
while(endA.next != null){
len++;
endA = endA.next;
}
while(endB.next != null){
len--;
endB = endB.next;
}
if(endA != endB){
return null;
}
if(len > 0){
while(len > 0){
headA = headA.next;
len--;
}
}else{
while(len < 0){
headB = headB.next;
len++;
}
}
while(headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA;
}
if((cycleA == null && cycleB != null) || (cycleA != null && cycleB == null)){
return null;
}
if(cycleA != null && cycleB != null){
return cycleA;
}
return null;
}

public ListNode detectCycle(ListNode head){
if(head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
slow = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}

总结

链表能够掌握好如何解决上述一些问题,就能够一通百通,关键在于结构的特性,如何利用这些特性去解决问题,还有快慢指针的作用也要梳理清楚

链表,搞定√