给定链表的头指针和一个节点指针,在O(1)时间删除该节点。
时间: 2023-05-10 17:56:09 浏览: 76
可以通过将该节点的下一个节点的值复制到该节点,然后删除下一个节点来实现O(1)时间删除该节点。具体实现如下:
```c++
void deleteNode(ListNode* head, ListNode* node) {
if (!head || !node) return;
if (node->next) {
ListNode* next = node->next;
node->val = next->val;
node->next = next->next;
delete next;
} else if (head == node) {
delete node;
head = nullptr;
} else {
ListNode* cur = head;
while (cur->next != node) cur = cur->next;
cur->next = nullptr;
delete node;
}
}
```
这段代码可以在O(1)时间内删除给定链表的头指针和一个节点指针。
相关问题
给定一个链表,删除链表的倒数第n个节点并返回链表的头指针
可以通过快慢指针来解决此问题。首先,将快指针向前移动n步,然后同时移动快指针和慢指针,直到快指针到达链表的末尾。此时,慢指针指向的节点就是需要删除的节点的前一个节点。将其指向下下个节点即可删除倒数第n个节点。
下面是实现代码:
```
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head;
ListNode* slow = head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
if (!fast) {
return head->next;
}
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
```
给定头节点,编写一个可以输出反转链表的编程代码
可以使用迭代或递归的方式实现反转链表。以下是用迭代方式实现的代码:
```python
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
这个函数接受链表的头节点作为参数,返回反转后的链表的头节点。它的实现方式是从头到尾遍历链表,每次将当前节点的 next 属性指向前一个节点,然后移动指针。最后返回反转后的链表的头节点。
如果你想要递归实现,可以使用类似下面这样的代码:
```python
def reverse_list(head):
if not head or not head.next:
return head
new_head = reverse_list(head.next)
head.next.next = head
head.next = None
return new_head
```
这个函数也接受链表的头节点作为参数,返回反转后的链表的头节点。它的实现方式是先递归反转剩余的部分,然后将当前节点的 next 属性指向前一个节点,并将前一个节点的 next 属性设为 None。最后返回反转后的链表的头节点。