链表也是多个元素的集合,但是这些元素在内存中并不是连续存储,而是通过额外存储的下一个节点指针来实现逻辑上的顺序连接。链表的节点一般由两个部分组成,一是数据,二是指向下一个节点的指针。链表有以下特点。
链表的优点有,删除和插入元素效率高,时间复杂度是O(1),但是访问特定节点效率低,需要逐个节点遍历。
例如,链表[1,2,3,4,5,6,7,8,9,10]
的存储结构如下:
存储的值
下一个节点的内存地址
内存地址
链表也是非常基础的数据结构,很多其它数据结构的底层数据存储方式都可以用链表来实现。比如说List、Stack、Queue等等。
常见的链表有以下这些。
1/**
2 * 自定义链表,实现增删改查
3 */
4class ZXLinkedList<T> {
5 /**
6 * 方便测试,初始容量设置小一点
7 */
8 private static final int DEFAULT_CAPACITY = 2;
9 private int size;
10 private Node head;
11
12 class Node {
13 T val;
14 Node next;
15
16 Node(T val) {
17 this.val = val;
18 }
19 }
20
21 public int size() {
22 return size;
23 }
24
25 public void add(T value) {
26 if (head == null) {
27 head = new Node(value);
28 } else {
29 Node n = head;
30 while (n.next != null) {
31 n = n.next;
32 }
33 n.next = new Node(value);
34 }
35 size++;
36 }
37
38 public void remove(int index) {
39 if (index >= size || index < 0) {
40 throw new ArrayIndexOutOfBoundsException(index);
41 }
42 if (index == 0) {
43 head = head.next;
44 } else {
45 Node n = head;
46 while (--index > 0) {
47 n = n.next;
48 }
49 n.next = n.next.next;
50 }
51 size--;
52 }
53
54 public void set(int index, T value) {
55 if (index >= size || index < 0) {
56 throw new ArrayIndexOutOfBoundsException(index);
57 }
58 Node n = head;
59 while (index-- > 0) {
60 n = n.next;
61 }
62 n.val = value;
63 }
64
65 @SuppressWarnings("unchecked")
66 public T get(int index) {
67 if (index >= size || index < 0) {
68 throw new ArrayIndexOutOfBoundsException(index);
69 }
70 Node n = head;
71 while (index-- > 0) {
72 n = n.next;
73 }
74 return (T) n.val;
75 }
76
77 @Override
78 public String toString() {
79 StringBuilder sb = new StringBuilder("[");
80 Node n = head;
81 for (int i = 0; i < size; i++) {
82 sb.append(n.val);
83 if (i != size - 1) {
84 sb.append(",");
85 } else {
86 sb.append("]");
87 }
88 n = n.next;
89 }
90 return sb.toString();
91 }
92}
93
94public class Main {
95
96 public static void main(String[] args) {
97 ZXLinkedList<Integer> list = new ZXLinkedList<>();
98 for (int i = 0; i < 20; i++) {
99 list.add(i);
100 }
101 assert list.size() == 20;
102 list.remove(list.size() - 1);
103 assert list.size() == 19;
104 list.set(0, 99);
105 assert list.get(0) == 99;
106
107 System.out.println(list);
108 }
109}
110
跟链表相关的题目,最经典的应该就是下面这道链表反转的题目。
给你单链表的头节点head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
链表可以选用迭代或递归方式完成反转。
另外一道经典的题目,检测链表是否有环。
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:你能用 O(1)(即,常量)内存解决此问题吗?
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
3→2→0→-4
↑_____↓
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
1→2
↑_↓
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
提示:
判断是否有环,实际上也可以理解为链表节点是否会重复,所以最容易想到的是遍历链表,然后用哈希表来判断节点是否有重复,这种解法空间复杂度为O(N)。下面介绍一种O(1)的解法,还是用之前提到的双指针的技巧,准确来讲应该叫快慢指针,因为每一轮循环第一个指针(快指针)会走两步,而慢指针只走一步,这样如果链表有环的话,两个指针最终会在同一个节点相遇。