链表的数据结构

1
2
3
4
5
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

新建链表

带头结点

带头节点的链表:此种链表保存数据是从head->next开始的,head中并未保存有数据,访问时自然head->next开始,优点就是方便操作。

头插法

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* createList() {
ListNode* head = new ListNode(0);
ListNode* node = head;
vector<int> nums = { 1,2,3 };
for (int i = 0; i < nums.size(); ++i) {
ListNode * temp = new ListNode(nums[i]);
temp->next = node->next;
node->next = temp;
}

return head;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* createList() {
ListNode* head = new ListNode(0);
ListNode* node = head;
vector<int> nums = { 1,2,3 };
for (int i = 0; i < nums.size(); ++i) {
ListNode * temp = new ListNode(nums[i]);
node->next = temp;
node = temp;
}
node->next = nullptr;
return head;
}

不带头结点

不带头节点的链表:此种链表的head即保存第一个数据,访问时从head开始。不利于删除或者添加指定位置数据的操作。

头插法

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* createList() {
ListNode* head = nullptr;
ListNode* node = nullptr;
vector<int> nums = { 1,2,3 };
for (int i = 0; i < nums.size(); ++i) {
node = new ListNode(nums[i]);
node->next = head;
head = node;
}

return head;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* createList() {
ListNode* head = nullptr;
ListNode* temp = head;
ListNode* node = nullptr;
vector<int> nums = { 1,2,3 };
for (int i = 0; i < nums.size(); ++i) {
node = new ListNode(nums[i]);
if (!head) {
head = node;
}
else {
temp->next = node;
}
temp = node;
}
if (!temp) {
temp->next = nullptr;
}

return head;
}

以下都使用带头结点的链表实现

打印链表

1
2
3
4
5
6
7
8
void printList(ListNode* head) {
ListNode* node = head;
while (node->next) {
node = node->next;
cout << node->val << " ";
}
cout << endl;
}

指定位置插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* insert(ListNode* head, int pos, int elem) {
ListNode* temp = head;
int i = 0;
//首先找到插入节点的上一节点,即pos-1位置
while ((temp->next != nullptr) && (i < pos - 1)) {
temp = temp->next;
++i;
}
if (!temp || i > pos - 1) {
cout << "Insert False!" << endl;
return temp;
}
ListNode* node = new ListNode(elem);
node->next = temp->next;
temp->next = node;
return head;
}

链表中查找某个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int searchNode(ListNode* head, int elem) {
ListNode* node = head;
int pos = 0;
int i = 1;
while (node->next) {
node = node->next;
if (elem == node->val) {
pos = i;
cout << "元素: " << elem << " 在链表中的位置是:" << pos << endl;
return pos;
}
++i;
}
cout << "search eoor!" << endl;
return -1;
}

修改某节点的数据

1
2
3
4
5
6
7
8
9
ListNode* replaceNode(ListNode* head, int pos, int elem) {
ListNode* node = head;
node = node->next;
for (int i = 1; i < pos; ++i) {
node = node->next;
}
node->val = elem;
return head;
}

获取链表长度

1
2
3
4
5
6
7
8
9
10
int sizeList(ListNode* head) {
int size = 0;
ListNode* node = head;
while(node->next) {
++size;
node = node->next;
}
cout << "链表的长度是: " << size << endl;
return size;
}

判断链表是否为空

1
2
3
4
5
6
7
8
bool isEmptyList(ListNode* head) {
if (!head) {
cout << "链表为空!" << endl;
return true;
}
cout << "链表不为空!" << endl;
return false;
}

删除链表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* deleteNode(ListNode* head, int pos) {
ListNode* node = head;
int i = 0;
while (node->next && i < pos - 1) {
node = node->next;
++i;
}
if (!node || i > pos - 1) {
cout << "delete false!" << endl;
return node;
}
ListNode* del = node->next;
node->next = del->next;
delete del;
del = nullptr;
return head;
}

清空链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void clearList(ListNode* head) {
ListNode* node = head;
ListNode* temp;
if (!head) {
cout << "链表为空!" << endl;
}
while (node->next) {
temp = node->next;
delete node;
node = temp;
}
delete node;
delete temp;
node = nullptr;
temp = nullptr;
head->next = nullptr;
cout << "链表清空!" << endl;
}

链表销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void destoryList(ListNode* head) {

if (!head) {
cout << "链表为空!" << endl;
}
ListNode* node = nullptr;
while (head->next) {
node = head->next;
delete head;
head = node;
}
if (head) {
delete head;
head = nullptr;
}
cout << "链表销毁成功!" << endl;

}