剑指offer2之删除链表结点

前言

在单链表中删除一个节点，一般都是从链表的头节点开始顺序遍历，然后在链表中删除。但是这样的时候复杂度为 O(n)，那么能不能在 O(1) 时间内删除元素呢？

题目一(删除链表的结点)

给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间删除该节点。链表结点与函数的定义如下：

struct ListNode{
  int val;
  ListNode* next;
}

void DeleteNode(ListNode** head, ListNode* pToBeDeleted);

算法思路

首先，我们应该先考虑删除位置的情况。所以需要讨论删除位置在头节点、链表中以及链表尾部。然后，要实现在 O(1) 中删除节点，我们可以将待删除节点的下一节点的信息赋值给前一节点，那么现在只需要删除原待删除节点的下一节点即可，因为已经知道了新的待删除节点的前一节点的指针了，所以操作便只需耗时 O(1)。

算法实现

复杂度分析

时间复杂度为 O(1)

题目二(删除链表中重复的结点)

题目：在一个排序的链表中，如何删除重复的节点。(无头节点)

算法思路

首先，为了更方便地操作链表，我们需要给链表加一个头结点。然后，我们需要两个指针 p 和 pre，分别表示指向当前节点和指向当前节点的前一节点。接着，需要判断当前节点和其下一节点是否存在重复节点，如果不存在则指针依次前移，继续遍历；否则从重复的第一个节点开始，循环跳过重复的节点并删除重复节点，最后 p 指针指向了第一个不重复的节点，然后只需把 pre 指针指向的节点和这个第一个不重复的节点连接即可,之后继续遍历。

算法实现

复杂度分析

需要遍历整个链表，所以时间复杂度为 O(n)。

参考

<<剑指offer2>>