题目一
在 O(1)时间内删除链表节点, 已知删除节点的指针.
思路
关键是已知删除节点的指针, 则可以将下一个节点复制到当前节点, 再将当前节点指向下下个节点.
这样相当于用到的是 当前节点, 下个节点, 下下个节点, 因此当前节点是尾节点时, 下下个节点不存在, 此时需要老老实实遍历寻找.
时间复杂度 [(n-1)*O(1) + O(n)] / n = O(1)
代码略.
题目二
在一个排序的链表中, 存在重复的结点, 请删除该链表中重复的结点, 重复的结点不保留, 返回链表头指针. 例如, 链表 1->2->3->3->4->4->5 处理后为 1->2->5
思路
思想很朴素, 就双指针不断检查.
唯一需要注意的是, 头指针也可能被删除, 因此设置一个 dummy, 这也是链表中经常用的 trick
- class Solution {
- public:
- ListNode* deleteDuplication(ListNode* pHead)
- {
- ListNode* dummy = new ListNode(-1);
- dummy->next = pHead; // 设置头节点, 防止头节点被删除
- ListNode* head = pHead, *pre = dummy, *pNext = nullptr;
- while (head && head->next)
- {
- pNext = head->next;
- if (head->val == pNext->val)
- {
- while (head->val == pNext->val && pNext) // 保证 pNext 存在, 比如当重复直到尾节点时
- {
- pNext = pNext->next;
- }
- pre->next = pNext;
- head = pNext;
- }
- else{
- pre = head;
- head = head->next;
- }
- }
- return dummy->next;
- }
- };
来源: http://www.bubuko.com/infodetail-2692345.html