常用链表结构
基本的链表结构，例如单向链表、双向链表的使用较为常见，不再介绍
而对于几种集合结构：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
|
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;
}
}
|
反转双向链表
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 Solution {
public boolean isPail (ListNode head) {
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 Solution {
public boolean isPail (ListNode head) {
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;
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;
}
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 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 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
|
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
|
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
|
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
|
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;
}
}
|
总结
链表能够掌握好如何解决上述一些问题，就能够一通百通，关键在于结构的特性，如何利用这些特性去解决问题，还有快慢指针的作用也要梳理清楚
链表，搞定√
