删除单链表(带头结点,头插入法建立单链表)的第i个结点,代码
时间: 2024-05-05 19:17:23 浏览: 142
以下是删除单链表的第i个结点的代码实现。其中,head为头结点指针,i为待删除结点的位置。
```c++
void deleteNode(ListNode* head, int i) {
ListNode* p = head->next;
ListNode* pre = head;
int j = 1;
while (p && j < i) {
pre = p;
p = p->next;
j++;
}
if (!p || j > i) {
cout << "删除位置无效" << endl;
return;
}
pre->next = p->next;
delete p;
}
```
思路解析:
从头结点的下一个节点开始循环查找,记录当前节点位置和前一个节点位置,直到找到待删除节点或者遍历完整个链表。
如果找到待删除节点,将前一个节点的next指向待删除节点的next,然后删除待删除节点。
如果没有找到待删除节点,说明删除位置无效,直接输出提示信息即可。
相关问题
删除单链表(带头结点,头插入法建立单链表)的第i个结点
需要遍历单链表,找到第i-1个结点,将其next指向第i+1个结点即可。具体实现如下:
```python
def delete_node(head, i):
if i <= 0:
print("Invalid index!")
return False
p = head
j = 0
while p.next and j < i-1:
p = p.next
j += 1
if not p.next or j > i-1:
print("Index out of range!")
return False
q = p.next
p.next = q.next
del q
return True
```
其中,head为头结点,i为要删除的结点的位置。首先需要判断i是否合法,然后遍历单链表找到第i-1个结点p和第i个结点q,将p的next指向q的next,然后删除q。如果i超出了单链表的长度,则删除失败。如果删除成功,返回True,否则返回False。
删除单链表(带头结点,头插入法建立单链表)的第i个结点
删除单链表中的第i个节点通常涉及到以下几个步骤,假设我们有一个`ListNode`结构体表示链表节点,其中包含一个指向下一个节点的指针`next`和一个额外的`prev`指向前一个节点,这是为了方便在不破坏链表的情况下删除节点:
1. 验证输入:首先检查链表是否为空,以及索引 `i` 是否有效(大于0并且小于或等于链表的实际长度)。如果 `i` 等于 1,那么直接将头节点设置为第二个节点即可,因为头节点本身就是第一个元素。
2. 找到第 i 个节点:从头节点开始遍历链表,每次移动到下一个节点直到找到第 i - 1 个节点。同时保存第 i 个节点的前一个节点,这将是删除操作后的指针。
3. 删除节点:一旦找到了第 i 个节点,更新其前一个节点的 `next` 指向第 i+1 个节点,使其跳过被删除的节点。对于头节点的操作,由于没有前一个节点,可以简单地将头节点指向原本的第二个节点。
4. 返回链表:如果需要返回删除节点后的链表,现在就拥有新的头节点了。
以下是这个过程的一个伪代码示例:
```python
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
```
阅读全文
相关推荐













