单链表不带头结点的头插法

单链表不带头结点的头插法指的是每次在链表的头部插入一个新的节点。具体的实现步骤如下：

1. 创建一个新节点，并为其赋值。
2. 将新节点的指针域指向当前链表的头节点。
3. 将链表的头节点指向新节点。

下面是一个示例代码实现：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
    return head;
}

该函数接受一个链表的头节点指针和要插入的值，返回插入后的链表头节点指针。需要注意的是，每次插入都需要动态申请一个新节点，因此需要在适当的时候释放空间，避免内存泄漏。

相关问题

单链表不带头结点头插法

单链表不带头结点的头插法，即每次将新节点插入到链表的第一个位置。具体实现步骤如下：

1. 创建一个新节点，并将数据存储在该节点中。
2. 将新节点的 next 指针指向原链表的第一个节点。
3. 将链表的头指针指向新节点。

下面是一个示例代码：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
    return head;
}

删除单链表(带头结点,头插入法建立单链表)的第i个结点

删除单链表中的第i个节点通常涉及到以下几个步骤，假设我们有一个`ListNode`结构体表示链表节点，其中包含一个指向下一个节点的指针`next`和一个额外的`prev`指向前一个节点，这是为了方便在不破坏链表的情况下删除节点：

1. 验证输入：首先检查链表是否为空，以及索引 `i` 是否有效（大于0并且小于或等于链表的实际长度）。如果 `i` 等于 1，那么直接将头节点设置为第二个节点即可，因为头节点本身就是第一个元素。

2. 找到第 i 个节点：从头节点开始遍历链表，每次移动到下一个节点直到找到第 i - 1 个节点。同时保存第 i 个节点的前一个节点，这将是删除操作后的指针。

3. 删除节点：一旦找到了第 i 个节点，更新其前一个节点的 `next` 指向第 i+1 个节点，使其跳过被删除的节点。对于头节点的操作，由于没有前一个节点，可以简单地将头节点指向原本的第二个节点。

4. 返回链表：如果需要返回删除节点后的链表，现在就拥有新的头节点了。

以下是这个过程的一个伪代码示例：

def delete_node(head, i):
    if not head or i <= 0:
        return head
    
    current = head.next
    for _ in range(i - 1):
        if not current:
            return head
        current = current.next

    # 如果找到了第 i 个节点
    if current:
        if current.prev:
            current.prev.next = current.next
        else:  # 头节点的情况
            head = current.next
        del current

    return head