剑指Offer（第2版）面试题18：删除链表的节点

剑指 Offer（第2版）面试题 18：删除链表的节点 剑指 Offer（第2版）面试题 18：删除链表的节点题目一：在 O(1) 时间删除链表结点题目二：删除链表中重复的节点

剑指 Offer（第2版）面试题 18：删除链表的节点 题目一：在 O(1) 时间删除链表结点

题目来源：

28. 在 O(1) 时间删除链表结点LeetCode 237. 删除链表中的节点

算法：

得到要删除节点的下一个节点 pNext；将 pNext->val 赋给 node->val；让 node 指向 pNext->next；delete pNext。

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void deleteNode(ListNode *node) { ListNode *pNext = node->next; node->val = pNext->val; node->next = pNext->next; delete pNext; } };

复杂度分析：

时间复杂度：O(1)。

空间复杂度：O(1)。

题目二：删除链表中重复的节点

题目来源：29. 删除链表中重复的节点

代码 1：书上的版本，很长，但是没有内存泄漏

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *deleteDuplication(ListNode *head) { if (head == nullptr) return nullptr; ListNode *p = head, *pre = nullptr; while (p) { ListNode *pNext = p->next; bool needDelete = false; if (pNext && p->val == pNext->val) needDelete = true; if (needDelete) { int value = p->val; ListNode *pToBeDel = p; while (pToBeDel && pToBeDel->val == value) { pNext = pToBeDel->next; delete pToBeDel; pToBeDel = pNext; } if (pre == nullptr) head = pNext; else pre->next = pNext; p = pNext; } else { pre = p; p = p->next; } } return head; } };

代码 2：简化版，没有 delete 重复节点，存在内存泄漏

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *deleteDuplication(ListNode *head) { auto dummy = new ListNode(-1); // 建立虚拟头结点 dummy->next = head; // 虚拟头结点指向头结点 auto p = dummy; while (p->next) // p的下一个节点不为空 { auto q = p->next; // q的下一个节点不为空，且q的下一个节点的值等于p的下一个节点的值 while (q->next && q->next->val == p->next->val) q = q->next; // 如果q==p的下一个节点 p=q if (q == p->next) p = q; // 如果不是说明存在重复元素,则p指向q的下一个节点即非重复节点 else p->next = q->next; } return dummy->next; } };

复杂度分析：

时间复杂度：O(n)，其中 n 是链表的长度。

空间复杂度：O(1)。