用尾插入法建立一个单链表
时间: 2023-04-07 08:01:04 浏览: 93
可以回答这个问题。尾插入法建立单链表的步骤如下:
1. 定义一个结构体来表示链表中的每个节点,包括数据域和指向下一个节点的指针域。
2. 定义一个头指针和一个尾指针,初始时它们都指向 NULL。
3. 读入第一个节点的数据,创建一个新节点,并将头指针和尾指针都指向这个节点。
4. 读入下一个节点的数据,创建一个新节点,并将尾指针的 next 指针指向这个节点,然后将尾指针指向这个新节点。
5. 重复步骤 4 直到读完所有节点的数据。
这样就可以用尾插入法建立一个单链表了。
相关问题
使用for循环尾插法建立一个单链表
好的,以下是使用for循环尾插法建立一个单链表的示例代码:
```C++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 尾插法建立单链表,返回链表头节点指针
ListNode* createList(int n) {
// 定义头节点,其val值为0,next指向NULL
ListNode* head = new ListNode(0);
// 定义尾节点指针tail,初始值指向头节点
ListNode* tail = head;
// 依次插入n个节点
for (int i = 1; i <= n; i++) {
// 读入节点值
int x;
cin >> x;
// 创建新节点
ListNode* newNode = new ListNode(x);
// 将新节点插入到尾部
tail->next = newNode;
// 更新尾节点指针
tail = newNode;
}
// 返回链表头节点指针
return head->next;
}
// 打印链表
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
int main() {
// 读入链表长度
int n;
cin >> n;
// 建立链表
ListNode* head = createList(n);
// 打印链表
printList(head);
return 0;
}
```
以上代码中,我们通过定义链表节点结构体 `ListNode` 和使用for循环尾插法来建立单链表。同时,我们也提供了打印链表的函数 `printList`。
删除单链表(带头结点,尾插入法建立单链表)的第i个结点
要删除单链表的第i个结点,需要先遍历到该结点的前一个结点,然后修改前一个结点的指针,使其指向第i+1个结点,最后删除第i个结点即可。
具体的实现过程如下:
```python
def delete_node(head, i):
"""
删除单链表的第i个结点
:param head: 单链表的头结点
:param i: 要删除的结点的索引,从1开始
:return: 删除结点后的单链表头结点
"""
if i <= 0:
return head # i小于等于0,直接返回原链表
index = 1 # 当前遍历到的结点的索引
cur = head.next # 当前遍历到的结点
pre = head # 当前遍历到的结点的前一个结点
while cur:
if index == i:
pre.next = cur.next # 修改前一个结点的指针
cur.next = None # 删除当前结点
return head
pre = cur
cur = cur.next
index += 1
return head # 遍历完整个链表,未找到对应的结点,直接返回原链表
```
其中,head为单链表的头结点,i为要删除的结点的索引,从1开始。如果i小于等于0,则直接返回原链表。遍历单链表,通过index变量记录当前遍历到的结点的索引,当index等于i时,说明找到了要删除的结点,此时修改前一个结点的指针,使其指向第i+1个结点,然后删除第i个结点即可。
如果遍历完整个链表,未找到对应的结点,则直接返回原链表。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)