最近看到面试算法题经常出现链表相关的题目,但是由于时间久远+oi中链表并不经常出现,我的链表知识已经还给刘汝佳了,遂恶补一通

定义

1
2
3
4
struct ListNode {
int value;
ListNode* next;
};

两个字段:一个是值,一个是指向下个节点指针。

添加节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void AddToTail(ListNode** pHead, int value) {
//new node
ListNode* pNew = new ListNode();
pNew->value = value;
pNew->next = NULL;

//head judge
if (*pHead == NULL) {
*pHead = pNew;
} else {
//find tail
ListNode* pNode = new ListNode();
pNode = *pHead;

while (pNode->next != NULL) {
pNode = pNode->next;
}

//add to tail
pNode->next = pNew;
}

}

这里没有直接使用结构体存储链表,而是使用结构体指针,仔细想了一下这么做的确是更合理的。

因为需要把一个结构体指针赋值给另一个结构体指针,便可以实现结构体的整体赋值。同时,可以使用->或者(*p).的方式调用结构体字段。

这里的入参pHead是链表的指针,由于链表是用指针的方式存储的,那么实际上pHead是指针的指针。

AddToTail函数可以分成四个部分,新建节点,判定是否为空链表,找末尾节点,添加节点。

理解原理之后手撸出来还是很简单的。

遍历并打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void PrintList(ListNode** pHead) {
//head judge
if (*pHead == NULL) {
cout << "the list is null";
return;
}

ListNode* pNode = *pHead;
while (pNode->next != NULL) {
cout << pNode->value << " ";
pNode = pNode->next;
}
cout << pNode->value;
}

这个挺简单的

删除第一次出现的某个值

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
void DeleteNode(ListNode** pHead, int value) {
//head judge
if (*pHead == NULL) {
cout << "the list is null";
return;
}

//first judge
if ((*pHead)->value == value) {
*pHead = NULL;
return;
}

bool flag = 0;
ListNode* pNode = *pHead;
while (pNode->next != NULL) {
if (pNode->next->value == value) {
flag = 1;
pNode->next = pNode->next->next;
break;
} else {
pNode = pNode->next;
}
}

}

这个也挺简单的,就是查找时要看向当下多看一个节点,这样可以使当前节点的next直接指向下下一个节点.

注意第一个节点带来的问题,建议第一个节点为空节点或者加上一段特判。