带头结点的单链表求前驱代码
时间: 2023-07-09 15:30:25 浏览: 64
以下是带头结点的单链表求前驱的代码实现:
```c++
// 带头结点的单链表结构体定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 求指定节点的前驱节点
ListNode* findPredecessor(ListNode* head, ListNode* target) {
ListNode* p = head;
while (p->next != NULL && p->next != target) {
p = p->next;
}
if (p->next == target) {
return p;
} else {
return NULL;
}
}
```
上述代码中,`findPredecessor` 函数接受两个参数:一个是带头结点的单链表的头结点指针 `head`,另一个是指定节点的指针 `target`。函数的返回值是指定节点的前驱节点指针,如果指定节点没有前驱,则返回 `NULL`。
函数的实现思路是从头结点开始遍历链表,找到指定节点的前一个节点即可。遍历过程中需要注意边界条件的处理。
相关问题
将输入的带头结点单链表倒置代码
以下是将带头结点的单链表倒置的代码:
```C++
void reverseList(Node* head) {
if (head == nullptr || head->next == nullptr) {
return; // 链表为空或只有一个节点,直接返回
}
Node* prev = nullptr;
Node* curr = head->next;
while (curr != nullptr) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
}
```
其中,`Node` 是单链表节点的结构体,包含一个 `int` 类型的数据成员 `data` 和一个指向下一个节点的指针 `next`。`head` 是指向链表头结点的指针,即 `head->next` 指向链表的第一个节点。在代码中,我们使用三个指针 `prev`、`curr` 和 `next`,分别表示当前节点的前驱、当前节点和当前节点的后继。在遍历链表的过程中,我们每次将当前节点的 `next` 指针指向它的前驱,然后将 `prev`、`curr`、`next` 分别向后移动一个节点,直到遍历完整个链表。最后,将头结点的 `next` 指针指向反转后的链表的第一个节点。
删除带头结点单链表head的第一个值为x的结点
要删除带头结点单链表head的第一个值为x的结点,可以按照以下步骤进行:
1. 定义两个指针p和pre,分别指向头结点和头结点的前驱结点(即空结点)。
2. 从头结点开始,依次遍历单链表,直到找到第一个值为x的结点。
3. 如果找到了值为x的结点,则让pre的next指向该结点的next,然后释放该结点的空间。
4. 如果遍历到链表末尾仍未找到值为x的结点,则输出提示信息。
下面是具体的代码实现:
```
void deleteNode(Node* head, int x) {
Node* p = head->next;
Node* pre = head;
while (p != NULL) {
if (p->data == x) {
pre->next = p->next;
free(p);
return;
}
pre = p;
p = p->next;
}
printf("未找到值为%d的结点\n", x);
}
```