O(1)删除链表节点 & 删除链表中的重复节点

O(1)删除链表节点：

代码实现：

void DeleteNode(ListNode **plist, ListNode *pToBeDelete) { if (plist == NULL || pToBeDelete == NULL) return; if (pToBeDelete->next != NULL) //要删除的点不是尾节点 { ListNode *pNext = pToBeDelete->next; pToBeDelete->val = pNext->val; pToBeDelete->next = pNext->next; delete pNext; pNext = NULL; } else //要删除的点是尾节点 { if (pToBeDelete == *plist) //只有一个节点 { delete pToBeDelete; pToBeDelete = NULL; *plist = NULL; } else //链表中有多个节点 { ListNode *pCurrrent = *plist; while (pCurrrent->next != pToBeDelete) pCurrrent = pCurrrent->next; pCurrrent->next = pToBeDelete->next; //等价于 pCurrrent->next = NULL； delete pToBeDelete; pToBeDelete = NULL; } } }

 

 删除链表中的重复节点：

分析： 有n个一样的节点，则这n个节点全部删除

代码实现：

ListNode* deleteDuplication(ListNode* pHead) { if (pHead == NULL) return pHead; ListNode *pre = NULL; //指向前面最晚访问过的不重复结点 ListNode *p = pHead; //指向当前处理的结点 ListNode *q = NULL; //指向当前处理结点后面结点 while (p != NULL) { //当前结点p，（其实是p指向当前结点），与它下一个结点p->next的val相同，说明要删掉有这个val的所有结点 if (p->next != NULL && p->next->val == p->val) { q = p->next; //找到q，它指向最后一个与p val相同的结点，那p 到 q （包含） 都是要删除的 while (q != NULL && q->next != NULL && q->next->val == p->val) { q = q->next; } //如果p指向链表中第一个元素，p -> ... -> q ->... , 要删除p到q, 将指向链表第一个元素的指针pHead指向q->next。 if (p == pHead) { pHead = q->next; } else//如果p不指向链表中第一个元素，pre -> p ->...->q ->... ，要删除p到q，即pre->next = q->next { pre->next = q->next; } //当前处理的p要向链表尾部移动 p = q->next; } else //p不是重复点 { pre = p; p = p->next; } } return pHead; }