一、知识
链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，链表分为：单链表、双链表、循环链表。
链表的插入和删除操作的时间复杂度： O(1) ，链表的随机访问的时间复杂度：O(n) 。
数组和链表的对比：
- 插入、删除、随机访问对比
- 数组的缺点是大小固定，一经声明就要占用整块连续内存空间，链表本身没有大小的限制，天然地支持动态扩容。
二、应用
1. 如何基于链表实现 LRU 缓存淘汰算法？
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的（或者越靠近尾部的为最新访问的）。
当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部；
优化：引入散列表来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。
具体实现参考2.LRU缓存中的第三种方法（单链表+HashMap实现）
- 使用LinkedHashMap实现
- 双向链表+HashMap实现
- 将最近查询的以及最近添加的放入链表的末尾，当链表超过最大长度时，删除头节点所指向的节点（即为最近最少使用的缓存）实现缓存的固定容量
- 使用HashMap可以直接判断出链表中是否存在该key的缓存
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
| class LRUCache {
private class ListNode {
int key;
int val;
ListNode pre;
ListNode next;
public ListNode() {
}
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
private int capacity;
private ListNode head, tail;
private Map<Integer, ListNode> map;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (map.containsKey(key)) {
ListNode node = map.get(key);
node.pre.next = node.next;
node.next.pre = node.pre;
moveLast(node);
return node.val;
}
return -1;
}
public void put(int key, int value) {
ListNode node;
if (get(key) != -1) {
map.get(key).val = value;
return;
}
node = new ListNode(key, value);
map.put(key, node);
moveLast(node);
if (map.size() > capacity) {
map.remove(head.next.key);
head.next = head.next.next;
head.next.pre = head;
}
}
public void moveLast(ListNode node) {
node.pre = tail.pre;
tail.pre.next = node;
node.next = tail;
tail.pre = node;
}
}
|
- 单链表+HashMap实现
- 使用单链表，最近使用的缓存数据存放在链表的末尾，最近不使用的数据在链表的头部
- hashmap存放key以及key缓存节点对应的前驱节点（key->其缓存节点的前驱节点）
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
| class LRUCache {
private class ListNode {
int key;
int val;
ListNode next;
public ListNode() {
}
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
private int capacity;
private ListNode head, tail;
private Map<Integer, ListNode> map;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode();
tail = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
ListNode node = map.get(key);
ListNode cur = node.next;
if (cur != tail) {
node.next = cur.next;
map.put(key, tail);
map.put(cur.next.key,node);
moveLast(cur);
}
return cur.val;
}
public void put(int key, int value) {
ListNode node;
if (get(key) != -1) {
map.get(key).next.val = value;
return;
}
node = new ListNode(key, value);
map.put(key, tail);
moveLast(node);
if (map.size() > capacity) {
map.remove(head.next.key);
head.next = head.next.next;
map.put(head.next.key, head);
}
}
public void moveLast(ListNode node) {
tail.next = node;
node.next = null;
tail = node;
}
}
|
- 将链表中的字符串添加至集合中，使用双指针遍历集合判断回文
- 使用快慢指针找到链表的中点（链表长度为偶数则为第二个中间），将中点后的链表反转，再将反转链表与原链表dui’bi
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
| class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode node = reverse(slow);
while (node != null) {
if (node.val != head.val) {
return false;
}
node = node.next;
head = head.next;
}
return true;
}
public ListNode reverse(ListNode node) {
if (node == null) {
return null;
}
ListNode head = node;
node = node.next;
head.next = null;
while (node != null) {
ListNode cur = node;
node = node.next;
cur.next = head;
head = cur;
}
return head;
}
}
|
两种方法:
- 遍历
- 引入头节点，遍历链表，将遍历得到的节点插入到头节点的后一个节点，最后得到的链表为反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode first = new ListNode();
while (head != null) {
ListNode cur = head;
head = head.next;
cur.next = first.next;
first.next = cur;
}
return first.next;
}
}
|
- 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
|
使用快慢指针，当链表不存在环时，当节点指向为null时结束，当链表存在环时，快指针和慢指针总会在环中相遇，当快指针和慢指针指向的节点相同时结束循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null) {
if (fast.next != null) {
fast = fast.next.next;
} else {
break;
}
slow = slow.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
|
创建头节点简化操作，遍历list1和list2链表比较大小，当一个链表遍历完后即可将另一链表直接添加至头节点链表的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode cur = head;
while (list1 != null && list2 != null) {
if (list1.val > list2.val) {
cur.next = list2;
list2 = list2.next;
} else {
cur.next = list1;
list1 = list1.next;
}
cur = cur.next;
}
cur.next = list1 == null ? list2 : list1;
return head.next;
}
}
|
创建头节点（不创建需要对特殊情况进行处理，比如：删除头节点），使用双指针首先快指针现遍历n个节点然后两个指针一同遍历，当快指针指向null时慢指针位于要删除节点的前一节点，接下来进行删除操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = new ListNode(0, head);
ListNode fast = head;
ListNode slow = first;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return first.next;
}
}
|
使用快慢指针，1. 当链表长度为偶数时，快指针最终指向null时结束遍历，这时慢指针指向链表的第二个中间节点。2. 当链表长度为奇数时，快指针指向最后一个节点结束遍历，这时慢指针指向链表的中间节点。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
|