【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点

本文主要是介绍【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣对应题目链接：LCR 136. 删除链表的节点 - 力扣（LeetCode）

---

一、《剑指 Offer》内容

---

二、分析题目

1、信息交换法

《剑指Offer》上给的这段代码，我把它称为信息交换法。
这道题其实考察了我们对链表的操作和时间复杂度的理解。

一般来讲，正常的解法时间复杂度都是 O(N)，因为我们要找到待删除节点，不得不牺牲 O(N) 的时间复杂度。那么 O(1) 的时间复杂度是如何实现的呢？这里有一个信息交换法，即：假如 head 为 4 -> 5 -> 1 -> 9，val 为 5 -> 1 -> 9，表示我们要删除结点 5，这时我们使用信息交换，把 val 改为 1 -> 9的信息即可。为什么呢？因为我们把待删除节点的后一个元素赋值给待删除节点，也就相当于删除了当前元素。但也可以举出反例：如果 val 的值是最后一个元素 9 呢？我们无法找到 9 的后一个元素（因为没有），只能重头开始找待删除元素 9，这样的话时间复杂度再次变成了 O(N)。这就是这道题目有意思的地方，如果删除节点为前面的 n−1 个节点，时间复杂度均为 O(1)，只有删除节点为最后一个的时候，时间复杂度才会变成 O(n)。平均时间复杂度为：(O(1)×(n−1)+O(n))/n=O(1)，仍然为 O(1)。

---

【常规写法】

 2、单指针

要删除链表中节点值为 val 的节点，只需要进行如下两步操作：

1. 找到待删除节点的前一节点 cur；
2. 将 cur->next 设置为 cur->next->next。

注意：头节点可能是待删除的节点。 

---

3、双指针

1. 设置两个指针分别指向头节点，pre （待删除节点的前一节点）和 cur (当前节点)；
2. 遍历整个链表，查找节点值为 val 的节点，找到了就删除该节点，否则继续查找。

• 2.1. 找到，将当前节点的前驱节点（pre 节点或者说是之前最近一个值不等于 val 的节点）连接到当前节点（cur 节点）的下一个节点（pre->next = cur->next）。
• 2.2. 没找到，继续遍历（cur = cur->next），更新最近一个值不等于 val 的节点（pre = cur）。

---

4、递归

递归的终止条件：

1. 该节点为空节点，直接返回。

2. 该节点就是要删除的节点，返回该节点的下一个节点。

---

5、设置虚拟（哨兵）头结点

之前的三种方法都需考虑头节点是否是待删除的节点，并且删除头节点的代码逻辑与删除非头节点的特别相似，可通过在头节点前面增加虚拟头节点，避免单独将拎头节点出来考虑，但是需要注意：返回的是虚拟头节点的下一节点而不是虚拟头节点。

注意：由于题目已明确是一个要删除的节点的值，因此找到该节点并删除之后，无需再遍历。

---

三、代码

1、参考代码

//更符合《剑指Offer》上题目的代码
class Solution {
public:ListNode* deleteNode(ListNode* head, ListNode* deleteNode) {if(head==nullptr || deleteNode==nullptr) return nullptr;// 要删除的节点不是尾节点if(deleteNode->next != nullptr){ListNode* nextNode = deleteNode->next;deleteNode->val = nextNode->val;deleteNode->next = nextNode->next;}// 链表只有一个节点，删除头节点（也是尾节点）else if(head == deleteNode){delete deleteNode;deleteNode = nullptr;head = nullptr;}// 链表中有多个节点，删除的节点是尾节点else{ListNode* p = head;//while(p->next != deleteNode) //另一种写法while(p->next != nullptr && p->next->next != nullptr){p = p->next;}p->next = nullptr;delete deleteNode;deleteNode = nullptr;}return head;}
};

---

2、对应题目代码

//单指针
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head->val==val) return head->next;ListNode* cur=head;while(cur->next && cur->next->val!=val)cur=cur->next;if(cur->next)cur->next=cur->next->next;return head;}
};//双指针
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head->val==val) return head->next;ListNode* prev=head;ListNode* cur=head;while(cur && cur->val!=val){prev=cur;cur=cur->next;}if(cur)prev->next=cur->next;return head;}
};//递归
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head==NULL) return head;head->next=deleteNode(head->next, val);if(head->val==val) return head->next;else return head;}
};//设置虚拟头结点
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {ListNode* newHead=new ListNode(0);newHead->next=head;ListNode* cur=newHead;while(cur->next){if(cur->next->val==val){cur->next=cur->next->next;break;}else{cur=cur->next;}}return newHead->next;}
};

这篇关于【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---