一个单向链表，已知p节点其他位置.请你删除p节点

要删除单向链表中的节点p，我们需要找到其前一个节点pre，然后将pre的next指针指向p的下一个节点，即跳过p节点，最后释放p节点的内存即可。具体实现如下（假设链表节点的结构体定义为ListNode）：

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)。

相关问题

初始化一个长度已知的链表节点

初始化一个长度已知的链表节点通常涉及创建一系列的`ListNode`实例，并将它们链接起来形成一个单向链表。假设链表每个节点包含一个整数值和指向下一个节点的引用，你可以这样做：

// 假设你有一个名为ListNode的类，它有两个属性：val（存储节点值）和next（指向下一个节点）
int[] values = {1, 2, 3, 4, 5}; // 这里是你要初始化的值列表
ListNode dummyHead = new ListNode(0); // 创建一个虚拟头节点，用于简化后续插入操作
ListNode current = dummyHead; // 当前节点指针

for (int value : values) {
    ListNode newNode = new ListNode(value); // 创建新的节点
    newNode.next = current.next; // 将新节点的next指向当前节点的下一个位置
    current.next = newNode; // 更新当前节点的next
    current = newNode; // 移动到新节点
}

// 结果，dummyHead.next就是你的链表的头部

这个过程完成后，`dummyHead.next`会指向最后一个元素，因为我们在最后一步时把`current`设置为了`newNode`。

已知一个单向链表的头，请写出删除其某一个结点的算法，要求，先找到此结点，然后删除

在单向链表中删除某个节点通常涉及到三个步骤：定位目标节点、检查节点是否存在以及更新链表结构。这里假设我们有一个指针`head`指向链表的头节点。

1. **定位目标节点**：首先，我们需要遍历链表，从头节点开始，直到找到目标节点或者链表结束。可以使用一个临时指针`current`和一个条件`found`来辅助查找过程。

struct Node* targetNode = NULL;
bool found = false;

while (head != NULL && !found) {
    if (head->data == targetValue) {
        targetNode = head;
        found = true;
    } else {
        head = head->next;
    }
}

这里假设链表节点包含一个`data`字段，`targetValue`是我们要找的值。

2. **检查节点是否存在**：如果`targetNode`为空，说明目标节点不存在于链表中，此时可以返回错误信息或者不做任何操作。

3. **删除节点**：一旦找到目标节点，我们需要处理两个情况：当前节点是头节点（即链表长度大于1），或者不是头节点。如果是头节点，将`head`指向下一个节点；如果不是头节点，则只需将`targetNode->next`指向`targetNode->next->next`即可。

if (targetNode != NULL) {
    if (head == targetNode) { // 头节点
        head = targetNode->next;
    } else {
        struct Node* prevNode = head;
        while (prevNode->next != targetNode) {
            prevNode = prevNode->next;
        }
        prevNode->next = targetNode->next;
    }
    // 释放目标节点的内存
    free(targetNode);
}

完成了以上步骤，我们就成功地删除了指定的节点。