题目描述:
题目一: 在 O(1)时间内删除链表节点 : 在给定的单向链表的头指针和一个节点指针, 定义一个函数在 O(1)时间内删除该节点.
- // 链表定义
- struct ListNode {
- int val;
- struct ListNode *next;
- ListNode(int x) :
- val(x), next(NULL) {
- }
- };
注意: 输入提供了要删除节点的指针!!
测试用例:
1)功能测试(从有多个节点的链表中删除中间, 头, 尾节点; 从只有一个节点的链表中删除唯一的节点)
2)特殊输入测试(头指针为 nullptr; 指向要删除的节点的指针为 nullptr)
解题思路:
1)常规做法: 平均时间复杂度为 O(n) 面试时不建议使用
遍历到要删除节点的前一个节点 pre, 将要删除节点的下一个节点赋值给前一个节点. pre->next = pCurrent->next;
2)不访问当前节点的前一个节点:
因为要删除节点的指针知晓, 则其下一个节点是可以访问的. 将下一个节点的值 (val 和 next) 赋值给当前节点, 然后删除下一个节点即可.
- pCurrent->val = pNext->val;
- pCurrent->next = pNext->next;
- delete pNext;
- pNext = nullptr;
题目描述:
题目二: 删除链表中重复的节点
在一个排序的链表中, 存在重复的结点, 请删除该链表中重复的结点, 重复的结点不保留, 返回链表头指针. 例如, 链表 1->2->3->3->4->4->5 处理后为 1->2->5
注: 虽然题目示例给的重复节点的个数都是 2, 但是题目中并没有明确指出. 因此要考虑重复节点为多个的情况. 如 1->2->3->3->3->4 处理后应该是 1->2->4
测试用例:
1)功能测试(重复节点位于链表的头部, 中间, 尾部; 链表中没有重复的节点)
2)特殊输入测试(指向链表头节点的指针为 nullptr; 链表中所有节点都是重复的)
解题思路:
1)由于链表是排序的, 只要考虑相邻元素值是否相等, 相等即重复.
如果当前节点与下一个节点值相同, 他们是重复的节点, 需要被删除. 为了保证删除之后链表仍然是相连的, 我们要把当前节点的前一个节点 (因此要定义 pPreNode) 与后面值比当前节点值大的节点相连.
- /*
- 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 pHead;
- ListNode* pPreNode = nullptr; // 先初始为空
- ListNode* pCurrentNode = pHead;// 指向第一个节点
- ListNode* pNext = nullptr;
- while(pCurrentNode!=nullptr){ //pCurrentNode->next!=nullptr
- // ListNode* pNext = pCurrentNode->next; //pNext 可能为空 // 不要放到循环里面定义, 每次循环都会定义
- pNext = pCurrentNode->next; //pNext 可能为空
- if(pNext!=nullptr && pCurrentNode->val==pNext->val){ //pNext 不为空时, 才可以访问其 val 值, 即 pNext->val 存在
- // 有重复节点
- // 删除重复节点
- int value = pCurrentNode->val;
- ListNode* pNodeToDel = pCurrentNode;
- while(pNodeToDel!=nullptr && pNodeToDel->val==value){ // 循环, 以遍历多个连续的重复值
- pNext = pNodeToDel->next; // pNodeToDel 会被删除, 要记录一下它的下一个节点, 否则之后就访问不到了
- delete pNodeToDel;
- pNodeToDel = nullptr;
- pNodeToDel = pNext; // 移动到下一个节点
- }
- // 重新连接链表
- if(pPreNode == nullptr){ // 说明时头节点
- pHead = pNext;
- }else{ // 非头节点
- pPreNode->next = pNext; //not pPreNode = pNext; 由于写错, 总报段错误!!! 不能把 pPreNode 直接指向 pNext
- }
- pCurrentNode = pNext; // 别忘了也要更新 pCurrentNode
- }else{
- // 没有重复节点
- pPreNode = pCurrentNode;
- //pCurrentNode = pNext;
- pCurrentNode = pCurrentNode->next;
- } // 无论是否删除节点, 每一次都要更新 pPreNode 与 pCurrentNode,pNext 会在每次循环初被更新
- }
- return pHead;
- }
- };
注意:
[1] delete 指针后一定先将指针置空. 因为不确定后面是否会在使用指针(会赋值), 如果不置空, 使用未定义的指针是十分危险的行为.
[2] 要区分删除的节点是否是头节点: line36 和 line38. 因为连接的操作是不同的
2)为了统一删除节点后, 头节点与其他节点的连接关系. 创建一个新的指针指向头指针.
- /*
- struct ListNode {
- int val;
- struct ListNode *next;
- ListNode(int x) :
- val(x), next(NULL) {
- }
- };
- */
- class Solution {
- public:
- ListNode* deleteDuplication(ListNode* pHead)
- {
- if(pHead==nullptr || pHead->next==nullptr) return pHead;
- ListNode* newpHead =new ListNode(-1);
- newpHead->next = pHead;
- ListNode* pPreNode = newpHead;
- ListNode* pNode = pHead;
- ListNode* pNext = nullptr;
- while(pNode!=nullptr){
- pNext = pNode->next;
- if(pNext!=nullptr && pNode->val==pNext->val){
- // 有重复节点
- ListNode* pToDel = pNode;
- int value = pNode->val;
- while(pToDel!=nullptr && pToDel->val==value){
- pNext = pToDel->next;
- delete pToDel;
- pToDel = nullptr;
- pToDel = pNext;
- }
- pPreNode->next = pNext;
- pNode = pNext; // 勿忘
- }else{
- // 没有重复节点
- pPreNode = pNode;
- pNode = pNext;
- }
- }
- return newpHead->next;
- }
- };
3)使用递归方法:
当头节点重复时, 直接移动头节点到第一个不重复的节点. 头节点不重复时, 移动到下一个节点, 剩余部分递归调用. 这样链表可以只处理头节点重复的情况.
- /*
- struct ListNode {
- int val;
- struct ListNode *next;
- ListNode(int x) :
- val(x), next(NULL) {
- }
- };
- */
- class Solution {
- public:
- ListNode* deleteDuplication(ListNode* pHead)
- {
- // 递归的终止条件
- if(pHead==nullptr || pHead->next==nullptr) return pHead;
- ListNode* pNode = nullptr;
- if(pHead->val==pHead->next->val){
- // 链表的头节点有重复
- int value = pHead->val;
- while(pHead!=nullptr && pHead->val==value){
- pNode = pHead->next;
- delete pHead;
- pHead=nullptr;
- pHead=pNode;
- }
- return deleteDuplication(pHead); // 因为输入的是头节点, 没有 next 指针接收, 因此直接 return
- }else{
- // 链表不重复
- pHead->next = deleteDuplication(pHead->next); // 返回的链表应该连接在头指针的下面
- }
- return pHead;
- }
- };
来源: http://www.bubuko.com/infodetail-2968453.html