单向链表操作

简介

链表(linked list)是一种常见的基础数据结构,它是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存放到其它节点的指针。单向链表的每个节点只有一个连接,指向下一个节点。和双向链表相比,单向链表的指针只能单向移动,功能自然也就受到了许多限制。不过单向链表耗用空间小,某些操作更快。

下面是节点数据结构的定义:

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

基本操作

遍历

printList函数遍历整个链表并打印节点内容,可用于调试:

1
2
3
4
5
6
7
void printList(ListNode *list)
{
for (ListNode *p = list; p != NULL; p = p->next) {
printf("%d->", p->val);
}
printf("null\n");
}

创建

createList函数构建链表。下面的代码中,使用一个标志节点dummy指向表头,这种处理方式很常见。许多书上直接将空的标志节点作为链表的头节点,但大多数的OJ平台并不这样,本文的代码和OJ兼容,可以直接拿去用。

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode *createList(vector<int> &nums)
{
ListNode dummy(-1);
ListNode *p = &dummy;

for (size_t i = 0; i < nums.size(); ++i) {
ListNode *node = new ListNode(nums[i]);
p->next = node;
p = p->next;
}

return dummy.next;
}

销毁

destroyList函数销毁链表,将内存释放:

1
2
3
4
5
6
7
8
9
10
void destroyList(ListNode *list)
{
ListNode *p = list;
list = NULL;
while (p != NULL) {
ListNode *next = p->next;
delete p;
p = next;
}
}

插入节点

insertFront函数从头部插入元素,操作很简单,将新节点插入到头节点之前,新节点成为链表的头节点:

1
2
3
4
5
6
7
ListNode *insertFront(ListNode *list, int val)
{
ListNode *node = new ListNode(val);
node->next = list;

return node;
}

insertBack函数从尾部插入元素,一路next到尾结点,将新节点放到尾节点的后面即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode *insertBack(ListNode *list, int val)
{
ListNode *node = new ListNode(val);
if (list == NULL) {
return node;
}

ListNode *p = list;
while (p->next != NULL) {
p = p->next;
}
p->next = node;

return list;
}

删除节点

deleteList函数首先找到指定节点,然后删除。删除链表的某个节点,必须知道它的前驱节点。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void deleteNode(ListNode *list, int val)
{
ListNode dummy(-1);
dummy.next = list;

ListNode *prev = &dummy;
ListNode *curr = list;
while (curr != NULL) {
if (curr->val == val) {
prev->next = curr->next;
delete curr;
return dummy.next;
}
prev = prev->next;
curr = curr->next;
}

return dummy.next;
}

反转链表

反转链表需要改变节点之间的连接方向,有迭代和递归两种写法。迭代算法从链表头开始,依次反转指针的指向,最后将原来的尾节点作为新链表的头节点。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode *reverseList(ListNode *list)
{
ListNode *prev = NULL;
ListNode *curr = list;
ListNode *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

递归算法将链表划分为两部分:首节点first和余下的部分rest,递归反转rest后,调整指针方向,将first变为rest的后继节点,整个链表即反转完毕。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *reverseList(ListNode *list)
{
if (list == NULL || list->next == NULL) {
return list;
}

ListNode *first = list;
ListNode *rest = list->next;
ListNode *reverted_rest = reverseList(rest);
rest->next = first;
first->next = NULL;

return reverted_rest;
}