单向链表基本介绍#
链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，实际上它是由节点（Node）组成，一个链表拥有不定数量的节点。其数据的存储位置不是连续的，而是分散在内存中，只有每个节点知道它下一个节点的存储位置。
链表中最常见的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。一个单向链表对的节点被分成两个部分，第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
单向链表的实现#
Java 中 LinkedList 的实现原理就是链表，这里我用 Java 语言手动实现一个简单的单向链表。代码如下。
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
129
| package com.realchoi.linkedlist;
/**
* 手动实现链表
*
* @author realchoi
*
*/
public class MyLinkedlist {
// 头节点
Node head = null;
/**
* 链表中的节点 ，data代表节点的对象，next代表指向的下一个节点
*
* @author realchoi
*
*/
class Node {
// 节点的引用，指向下一个节点
Node next = null;
// 节点的对象，即内容
int data;
// 构造方法
public Node(int data) {
this.data = data;
}
}
/**
* 向链表中插入数据（尾部插入）
*
* @param data
*/
public void addNodeAtLast(int data) {
// 实例化一个节点
Node newNode = new Node(data);
// 如果头节点为空，则将新建的节点设置为头节点
if (head == null) {
head = newNode;
return;
}
// 如果头节点不为空，则循环遍历已有的链表，找到链表的尾部
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
// 将新的节点加在链表的尾部
temp.next = newNode;
}
/**
* 向链表中插入数据（头部插入）
*
* @param data
*/
public void addNodeAtFirst(int data) {
// 实例化一个节点
Node newNode = new Node(data);
// 如果头节点为空，则将新建的节点设置为头节点
if (head == null) {
head = newNode;
return;
}
// 如果头节点不为空，则将原头节点直接连接到新节点的next，并将新增的节点设为新的头节点
newNode.next = head;
head = newNode;
}
/**
* 删除第index个节点（序号从1开始）
*
* @param index
* @return
*/
public boolean deleteNode(int index) {
if ((index < 1) || (index > length())) {
return false;
}
if (index == 1) {
head = head.next;
return true;
}
int i = 2;
Node preNode = head;
Node curNode = head.next;
while (curNode != null) {
if (i == index) {
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return false;
}
/**
* 获取链表的长度
*
* @return
*/
public int length() {
int length = 0;
Node temp = head;
while (temp.next != null) {
length++;
temp = temp.next;
}
return length;
}
/**
* 打印链表的内容
*/
public void printLinkedList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}
|
单向链表的反转#
迭代反转法#
迭代反转法是从前往后反转各个节点的指针域的指向。其基本思路是，将当前节点（ curNode）的下一个节点（ curNode.next）存储到临时节点（ tempNode）中，以免后续反转当前节点的指针域时把下一个节点给弄丢了，然后把当前节点的指针域的指向设置为上一个节点（ preNode）。原理图如下。
代码如下。
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
| /**
* 链表反转（使用迭代的方法）
*
* @param head
* 头节点
* @return 反转后的节点
*/
public static Node reverseByIteration(Node head) {
if (head == null || head.next == null) {
return head;
}
// 上一节点
Node preNode = head;
// 当前节点
Node curNode = head.next;
// 临时节点，用于保存当前节点指向的下一节点
Node tempNode;
// 当前节点为null时意味着位于尾节点
while (curNode != null) {
// 临时存储下一个节点，否则下一步操作后会把原来的下一个节点丢失
tempNode = curNode.next;
// 将当前节点的指针域反转指向上一个节点
curNode.next = preNode;
// 指针向后移动
preNode = curNode;
curNode = tempNode;
}
// 最后将头节点的指针域设为null
head.next = null;
// 返回新的头节点（原链表的尾节点）
return preNode;
}
|
递归反转法#
和迭代反转法相反，递归反转法，是利用递归，找到链表的尾节点，然后从尾节点开始反转各个节点的指针域。如下图所示。
实现代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* 链表反转（使用递归方法）
*
* @param head
* 头节点
* @return 反转后的节点
*/
public static Node reverseByRecursion(Node head) {
// 若当前链表为空，或者当前节点已经在尾节点，直接返回当前节点
if (head == null || head.next == null) {
return head;
}
// 先找到后续节点，从后往前进行反转
Node newHead = ReverseByRecursion(head.next);
// 将当前节点的指针域指向上一个节点
head.next.next = head;
// 上一个节点的指针域设为null
head.next = null;
// 返回新的头节点
return newHead;
}
|
参考资料#
[1]维基百科：链表
[2]【数据结构】链表的原理及 Java 实现
[3]Java 单链表反转详细过程