卡码网语言基础课 ｜链表的基础操作III

链表的插入操作

• 找到要插入的位置的前一个位置，将其命名为cur，将要插入的位置的下一个节点命名为tmp，他们之间的关系是cur -> next = tmp
• 创建一个链表newNode，将cur的next指针指向newNode，即cur -> next = nowNode
• 将newNode的next指针指向tmp，即newNode -> next = tmp

转换为代码如下：

// 创建了一个新的 ListNode 结构的节点，值为x, 并将其地址赋给指针 newNode
ListNode *newNode = new ListNode(x);
// 创建了一个名为 tmp 的指针，临时存储当前节点 cur 的下一个节点的地址。
ListNode *tmp = cur -> next;
// 将当前节点 cur 的 next 指针更新为指向新节点 newNode，将新节点插入到当前节点后面。
cur -> next = newNode;
// 将新节点 newNode 的 next 指针设置为指向之前临时存储的节点 tmp
newNode -> nxet = tmp
1
2
3
4
5
6
7
8

链表的删除操作

找到删除节点的前一个节点cur，并将其next指针设置为指向当前节点的下下个节点。

转换为代码如下：

cur -> next = cur -> next -> next;
1

打印链表

在函数内部定义一个指针cur，初始时指向链表的头节点head

当cur的的下一个节点不存在时（cur -> next = NULL）说明下一个节点为空节点，即链表的末尾

while (cur -> next != NULL) {
}
1
2

在循环体内打印当前节点cur的下一个节点（cur -> next）的值（val）。随后将cur更新为指向链表的下一个节点，以便在下一次循环中打印下一个节点的值。

while (cur -> next != NULL) {
	cout << cur -> next -> val << " ";
	cur = cur -> next;
}
1
2
3
4

循环体结束时，表示已经遍历完了整个链表。最后打印一个换行符，用于分隔不同的输出行。

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

代码编写

代码的基础结构以及定义链表的结构体如下：

#include 
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}
};

int main() {}
1
2
3
4
5
6
7
8
9
10

首先需要接收整数 k ，表示需要构建链表的长度：

int main () {
	int k, val;
	cin >> k;
}
1
2
3
4

然后我们需要构建一个长度为 k 的链表，同时记得创建虚拟头节点以及初始化一个指针cur指向它，方便后续节点的接入

ListNode *dummyHead = new ListNode(0);
ListNode *cur = dummyHead;
for (int i = 0; i < k; i++){
	cin >> val;
	ListNode *newNode = new ListNode(val);
	cur -> next = newNode;
	cur = cur -> next;
}
1
2
3
4
5
6
7
8

之后需要接收一个整数s表示s行输入，每行两个整数，第一个整数为 n，第二个整数为x，代表在链表的第n个位置插入x。

int s, n, x;
cin >> s;
while (s--) {
	cin >> n >> x;
}
1
2
3
4
5

当插入的位置n是一个小于等于0的数或者n大于链表的长度时，插入位置不合法。

需要注意，在插入后链表的长度会变化，所以我们需要提前定义一个变量listLen指代链表的长度

int listen = k;

if (n <= 0 || n > listLen) {
	cout << "Insertion position is invalid" << endl;
	continue;
}
1
2
3
4
5
6

如果不满足上面的条件，说明插入的位置合法，后续执行的操作是完成插入以及打印链表。

插入链表节点只需要找到插入位置的前一个节点即可，也就是第n - 1个节点，从虚拟头节点开始遍历，需要走n - 1步。

cur = dummyHead;
for (int i = 1; i < listLen; i++) {
	cur = cur -> next;
}
1
2
3
4

插入链表后需要将链表的长度 + 1：

// 插入节点
ListNode *newNode = new ListNode(x); // 构造一个新的节点
ListNode *tmp = cur -> next;
cur -> next = newNode;
newNode -> next = tmp;

// 链表长度加1
listLen++;
1
2
3
4
5
6
7
8

随后打印链表即可：

printLinkList(dummyHead);
1

链表节点删除的前置步骤类型，需要接收一个整数L，表示后续会有L行输入，每行一个整数m，代表删除链表中的第 m 个元素：

int l, m;
cin >> l;
while (l--) {
	cin >> m;
}
1
2
3
4
5

判断是否是非法输入

if (m <= 0 || m > listLen) [
	cout << "Deletion position is invalid." << endl;
	continue;
]
1
2
3
4

找到要删除节点的前一个节点

cur = dummyHead;
for (int i = 1; i < m; i++) cur = cur -> next;
cur -> next = cur -> next -> next;
listLen--;
if (listLen != 0) printLinklist(dummyHead);
1
2
3
4
5

完整代码如下：

#include 
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 打印链表
void printLinklist(ListNode* dummyHead) {
    ListNode* cur = dummyHead;
    
    while (cur->next != NULL) {
        cout << cur->next->val << " ";
        cur = cur -> next;
    }
    
    cout << endl;
}
int main() {
    int k, val;
    ListNode* dummyHead = new ListNode(0); // 创建了一个虚拟头结点
    
    cin >> k;
    int listLen = k; //记录链表长度，用来控制非法输入输出
    
    // 定义一个指向当前节点的指针 cur，初始指向虚拟头结点
    ListNode* cur = dummyHead; 
    
    for (int i = 0; i < k; i++) { // 或者使用while(n--)
        cin >> val;
        ListNode* newNode = new ListNode(val); // 构造一个新的节点
        cur -> next = newNode; // 将新节点接入链表
        cur = cur -> next;      // cur 指向下一个节点
    }
    
    // 增加节点
    int s, n, x;
    cin >> s;
    
    while (s--) {
        cin >> n >> x;
        
        if (n <= 0 || n > listLen) { // 当要插入的位置非法时
            cout << "Insertion position is invalid." << endl;
            continue;
        }
        
        // 指针重新指向虚拟头结点，准备用cur遍历链表
        cur = dummyHead;

        // 寻找添加节点的位置，i从1开始，因为节点计数从1开始
        for (int i = 1; i < n; i++) cur = cur->next;

        // 插入节点
        ListNode* newNode = new ListNode(x); // 构造一个新的节点
        ListNode* tmp = cur ->next;
        cur->next = newNode;
        newNode->next = tmp;

        // 链表长度加1
        listLen++;

        // 打印链表
        printLinklist(dummyHead);

    }

    // 删除节点
    int l,m;
    cin >> l;
    
    while (l--) {
        cin >> m;
        
        if (m <= 0 || m > listLen) {
            cout << "Deletion position is invalid." << endl;
            continue;
        }
        
        // 指针重新指向虚拟头结点，准备用cur遍历链表
        cur = dummyHead;

        //开始寻找删除节点的位置，i从1开始，因为节点计数从1开始
        for (int i = 1; i < m; i++) cur = cur->next;

        // 删除节点
        cur->next = cur->next->next;

        listLen--; // 链表长度减一

        // 如果删除节点后链表为空则不打印
        if (listLen != 0) printLinklist(dummyHead);
    }
}
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