数据结构之链表

链表是基本的线性存储的数据结构。


基本链表操作

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
#include <iostream>
using namespace std;
struct Node {
int val;
Node *next;
Node(int val) : val(val), next(NULL) {}
};
class List {
public:
void init(Node *node);
bool insert(int pos, Node *node);
bool find(int val);
bool del(int pos);
void print() const;
private:
Node *head;
Node *RecusionReverse(Node *head);
void InterationReverse();
};
void List::init(Node *node) {
if (head != NULL && node != NULL) {
head = node;
}
}
bool List::insert(int pos, Node *node) {
if (head == NULL) return false;
Node *pre = head;
if (pos == 0) {
node->next = head;
head = node;
} else {
for (int i=1; i<pos; ++i) {
if (pre->next == NULL) return false;
pre = pre->next;
}
node->next = pre->next;
pre->next = node;
}
return true;
}
bool List::find(int val) {
Node *node = head;
while (node != NULL) {
if (node->val == val) return true;
node = node->next;
}
}
bool List::del(int pos) {
if (head == NULL) return false;
Node *pre = head;
if (pos == 0) {
Node *tmp = head;
head = head->next;
delete tmp;
} else {
for (int i=1; i<pos; ++i) {
if (pre->next == NULL) return false;
pre = pre->next;
}
Node *tmp = pre->next;
pre->next = pre->next->next;
delete tmp;
}
return true;
}
void List::print() const {
Node *node = head;
while (node != NULL) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
int main() {
int n;
List list;
list.init(new Node(1));
list.insert(0, new Node(2));
list.insert(1, new Node(3));
list.insert(3, new Node(4));
list.print();
cout << list.find(3) << endl;
cout << list.find(9) << endl;
list.del(0);
list.del(1);
list.del(1);
list.print();
list.insert(0, new Node(2));
list.insert(1, new Node(3));
list.insert(3, new Node(4));
list.print();
return 0;
}

运行结果:

1
2
3
4
5
2 3 1 4
1
0
3
2 3 3 4


翻转链表

递归翻转

1
2
3
4
5
6
7
8
9
Node *List::RecusionReverse(Node *head) {
if (head->next == NULL) return head;
Node *newHead = RecusionReverse(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

迭代翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void List::InterationReverse() {
if (head == NULL || head->next == NULL) return;
Node *pre = NULL;
Node *cur = head;
Node *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head = pre;
}

链表中位数

1
2
3
4
5
6
7
8
9
10
11
int List::middle() const {
if (head->next == NULL) return head->val;
Node *fast = head;
Node *slow = head;
while ((fast = fast->next->next) != NULL) {
slow = slow->next;
}
return slow->val;
}