力扣对应题目链接：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 的节点，只需要进行如下两步操作：
- 找到待删除节点的前一节点 cur；
- 将 cur->next 设置为 cur->next->next。
注意：头节点可能是待删除的节点。
3、双指针
- 设置两个指针分别指向头节点，pre （待删除节点的前一节点）和 cur (当前节点)；
- 遍历整个链表，查找节点值为 val 的节点，找到了就删除该节点，否则继续查找。
- 2.1. 找到，将当前节点的前驱节点（pre 节点或者说是之前最近一个值不等于 val 的节点）连接到当前节点（cur 节点）的下一个节点（pre->next = cur->next）。
- 2.2. 没找到，继续遍历（cur = cur->next），更新最近一个值不等于 val 的节点（pre = cur）。
4、递归
递归的终止条件：
- 该节点为空节点，直接返回。
- 该节点就是要删除的节点，返回该节点的下一个节点。
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; } };
四、扩展：删除链表中重复的节点
牛客对应题目链接：删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)
核心考点 ：链表操作，临界条件检查，特殊情况处理。
1、《剑指Offer》(第2版) 对应内容
2、分析题目
这是一个排好序的链表，说明重复节点是连续的。
通过快慢指针的方式限定范围，进而达到去重的效果。
这里要考虑特别多的特殊情况，如：全部相同，全部不相同，部分相同等，为了方便解题我们定义头结点，主要是应对全部相同的情况。
3、代码
//牛客AC代码 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(pHead==nullptr) return nullptr; ListNode* newHead=new ListNode(0); //考虑到链表中的元素可能全部相同，所以构造一个头结点 newHead->next=pHead; //prev 永远在last的前面 ListNode* prev=newHead; ListNode* last=prev->next; while(last) { // 1.如果last和last->next不相等，就一直让prev和last往后走 while(last->next && last->val!=last->next->val) { prev=prev->next; last=last->next; } // 2. 如果如果last和last->next相等，就让last一直往后走 while(last->next && last->val==last->next->val) last=last->next; // 走到这里结果一共有三种,注意：prev永远指向的是前驱有效节点 // 1. last->next != nullptr 且 (prev, last] 限定了一段重复范围 // 2. last->next == nullptr 且 (prev, last] 限定了一段重复范围 // 最后相当于 prev->next = nullptr // 3. last->next == nullptr && prev->next == last 说明从本次循环开始， // 整个链表中的元素都不相同，此时就不需要进行去重(特殊情况) if(prev->next!=last) prev->next=last->next; last=last->next; } return newHead->next; } };
力扣对应题目链接：83. 删除排序链表中的重复元素 - 力扣（LeetCode）
力扣上面的这道题目和《剑指Offer》上的略微不同，它不是删除掉所有重复的元素，而是让每个元素只出现一次。
参考代码：
//力扣AC代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head==nullptr) return nullptr; ListNode* cur=head; while(cur->next) { if(cur->val==cur->next->val) cur->next=cur->next->next; else cur=cur->next; } return head; } };
