一个单向链表,已知p节点其他位置.请你删除p节点
时间: 2024-03-13 15:46:57 浏览: 19
要删除单向链表中的节点p,我们需要找到其前一个节点pre,然后将pre的next指针指向p的下一个节点,即跳过p节点,最后释放p节点的内存即可。具体实现如下(假设链表节点的结构体定义为ListNode):
```c++
void deleteNode(ListNode* p) {
if(!p) return; // p为空指针,直接返回
if(!p->next) { // p为尾节点,需要遍历找到pre
ListNode* cur = head;
while(cur && cur->next != p) {
cur = cur->next;
}
if(cur) cur->next = nullptr;
delete p;
return;
}
// p不为尾节点,直接删除
ListNode* next = p->next;
p->val = next->val;
p->next = next->next;
delete next;
}
```
需要注意的是,如果p为尾节点,则需要遍历整个链表找到其前一个节点pre,时间复杂度为O(n);如果p不为尾节点,则可以直接删除,时间复杂度为O(1)。
相关问题
已知head 指向一个带头结点的单向链表,链表中每个节点包含字符型数据和和指向本结构节点的指针,编写程序实现如下图所示的逆置
假设链表的头结点为head,可以按照以下步骤实现链表逆置:
1. 定义三个指针:p, q, r。其中p指向头结点,q指向第一个节点,r指向q的后继节点;
2. 将p的next指向空节点,表示新链表的结尾;
3. 依次遍历链表,对于每个节点,将q的next指向p,实现节点的逆置;
4. 将p、q、r依次向后移动一个节点,直到r指向空节点,表示遍历到了链表的尾部;
5. 将头结点的next指向q,表示新的头结点为原链表的尾节点;
6. 返回头结点head。
具体实现代码如下:
```c
void reverseList(Node *head) {
Node *p = head, *q = head->next, *r = q->next;
p->next = NULL;
while (r) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
head->next = q;
}
```
其中,Node为链表节点的结构体,包含数据和指向下一个节点的指针。
已知headz指针指向一个已建立的单向链表。链表中每个节点包含数据域(data)和指针域(next)。定义一个函数求链表中所有节点的数据域之和
可以使用一个循环遍历整个链表,将每个节点的数据域值累加起来即可求得链表中所有节点数据域之和。具体实现如下:
```c
int sumList(struct ListNode* headz) {
int sum = 0;
struct ListNode* cur = headz; // 定义一个指针指向链表头节点
while (cur != NULL) { // 循环遍历链表
sum += cur->data; // 将当前节点数据域值累加到 sum 变量中
cur = cur->next; // 将指针指向下一个节点
}
return sum; // 返回链表中所有节点数据域之和
}
```
其中,`struct ListNode` 是链表节点的结构体定义,包含数据域 `data` 和指针域 `next`,如下所示:
```c
struct ListNode {
int data;
struct ListNode* next;
};
```
需要注意的是,上述代码中的 `headz` 是链表的头节点指针,它指向链表中的第一个节点。如果链表为空,即 `headz` 指针为空,则函数直接返回 0。