【剑指offer】面试题13、在 O(1)时间上删除链表结点

题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下：
typedef struct Node
{
    int m_nValue;
    struct Node *m_pNext;
}ListNode, *pListNode;

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

　在单链表中删除一个结点，最常用的做法莫过于从链表的头结点开始，顺序遍历查找并找到要删除的结点，然后再进行删除操作。

　比如在下图（a）所示的链表中，我们想要删除结点 i，我们就可以从头结点开始遍历该链表，遍历到 h 结点时，会发现 h 的下一个结点 i 就是我们所要删除的结点。这样我们可以把 h 的 m_pNext指向 i 的下个结点 j。指针调整之后我们就可以安全删除结点 i 并保证链表没有断开。

这种顺序查找的时间复杂度为 O(n)。

之所以需要从头开始查找，是因为我们需要得到将被删除的前面一个结点。在单链表中，结点中没有指向前一个结点的指针，因此只好从链表的头结点开始顺序查找。

那么是不是一定需要得到被删除结点的前一个结点呢？答案是否定的。以上面（a）链表为例。我们可以很方便的得到要删除结点 i 的下一个结点 j。如果我们把下一个结点 j 的内容复制到欲删除结点 i 上，再把下个结点 j 删除，这样不就相当于把当前需要删除的结点 i 删除了么【实际删除的为结点 j 】。

上述思路还有个问题：如果我们要删除的结点位于链表的尾部呢。那么它就没有下个结点。这样我们就需要从链表的头结点开始，进行顺序遍历并删除。

最后还有一点：除了上面两种情况，还有个特例。就是链表中只有一个结点。上面的两种情况我们在进行删除操作时，不需要删除头结点。而当只有一个结点时，我们不仅要删除函数给出的结点pToBeDeleted，同时还要将链表的头结点设置为NULL。

完整的代码如下：

  1 // deleteNode.c
  2 #include "stdio.h"
  3 #include "stdlib.h"
  4 
  5 #define N 10
  6 
  7 typedef struct Node
  8 {
  9     int m_nValue;
 10     struct Node *m_pNext;
 11 }ListNode, *pListNode;
 12 
 13 void deleteNode(ListNode **pHead, ListNode *pToBeDeleted);
 14 // 获得要删除结点
 15 ListNode *getNodeIndex(ListNode *pHead, int index);
 16 
 17 void createList(ListNode **pHead, int len)
 18 {
 19     ListNode *pTail = NULL;
 20 
 21     while(len--)
 22     {
 23         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode));
 24         pNew->m_nValue = rand()%100;
 25         pNew->m_pNext = NULL;
 26 
 27         if(*pHead == NULL)
 28         {
 29             *pHead = pNew;
 30             pTail = pNew;
 31         }
 32         else
 33         {
 34             pTail->m_pNext = pNew;
 35             pTail = pNew;
 36         }
 37     }
 38 }
 39 
 40 void printList(ListNode *pHead)
 41 {
 42     while(pHead != NULL)
 43     {
 44         printf("%3d ", pHead->m_nValue);
 45         pHead = pHead->m_pNext;
 46     }
 47     printf("
");
 48 }
 49 
 50 void deleteNode(ListNode **pHead, ListNode *pToBeDeleted)
 51 {
 52     if(!pHead || !pToBeDeleted)
 53         return;
 54 
 55     // 链表有多个结点，并且删除的不是尾结点
 56     if(pToBeDeleted->m_pNext != NULL)
 57     {
 58         ListNode *pNext = pToBeDeleted->m_pNext;
 59         pToBeDeleted->m_nValue = pNext->m_nValue;
 60         pToBeDeleted->m_pNext = pNext->m_pNext;
 61 
 62         free(pNext);
 63         pNext = NULL;
 64     }
 65     // 还剩两种情况：要么链表只有一个结点，要么删除的是尾结点(含有多个结点)
 66     else if(*pHead == pToBeDeleted)// 链表只有一个结点
 67     {
 68         free(pToBeDeleted);
 69         pToBeDeleted = NULL;
 70         *pHead = NULL;
 71     }
 72     else // 多个结点，并且删除的是尾结点
 73     {
 74         ListNode *curNode = *pHead;
 75         while(curNode->m_pNext != pToBeDeleted) // 找到删除结点的前一个结点
 76             curNode = curNode->m_pNext;
 77 
 78         curNode->m_pNext = NULL;
 79         free(pToBeDeleted);
 80         pToBeDeleted = NULL;
 81     }
 82 }
 83 
 84 ListNode *getNodeIndex(ListNode *pHead, int index)
 85 {
 86     if(!pHead || index < 0)
 87         return NULL;
 88 
 89     ListNode *node = pHead; 
 90     while(--index)
 91         node = node->m_pNext;
 92     return node;
 93 }
 94 
 95 int main(int argc, char const *argv[])
 96 {
 97     ListNode *pHead = NULL;
 98 
 99     createList(&pHead, N);
100     printf("Before: ");
101     printList(pHead);
102 
103     ListNode *pToBeDeleted = getNodeIndex(pHead, 3);
104     deleteNode(&pHead, pToBeDeleted);
105     printf("After: ");
106     printList(pHead);
107 
108     return 0;
109 }

View Code

本文完。