单项链表在一个已知p节点之前插入一个q
时间: 2024-03-14 10:48:04 浏览: 93
好的,针对你的问题,可以使用如下的代码实现在一个已知p节点之前插入一个q节点的操作:
```
// 定义单链表的节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 在已知p节点之前插入一个q节点
void insertNode(ListNode* p, ListNode* q) {
if (p == NULL || q == NULL) return;
ListNode* pre = NULL;
ListNode* cur = p;
while (cur != q) {
pre = cur;
cur = cur->next;
}
if (pre == NULL) {
q->next = cur;
p = q;
} else {
pre->next = q;
q->next = cur;
}
}
```
在上述代码中,我们定义了单链表的节点结构体 `ListNode`,其中包括一个整数值和一个指向下一个节点的指针。接着,我们定义了 `insertNode` 函数,它接受两个参数:已知节点 `p` 和要插入的节点 `q`。
在函数中,我们首先判断 `p` 和 `q` 是否为空,如果有一个为空,则直接返回。接着,我们使用两个指针 `pre` 和 `cur` 遍历整个链表,找到 `p` 节点。当遍历到 `p` 节点时,我们将 `q` 节点插入到 `p` 之前。如果 `p` 是链表的头节点,则直接将 `q` 节点插入到 `p` 之前,并将 `p` 指向 `q`。否则,我们将 `q` 节点插入到 `p` 之前,并将 `pre` 指向 `q`,`q` 指向 `p`。
需要注意的是,如果链表中没有找到 `p` 节点,则不会进行任何操作。
阅读全文