题目
在O(1)时间内删除链表节点。
给定单项链表的头节点和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下：
typedef struct ListNode { int m_nValue; struct ListNode* m_pNext; }ListNode; void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted);
分析
线性查找
要删除的位置有三种情况
1、最后节点要删除，直接删除然后前一个结点指向NULL
2、头部(第一个存数据的节点)删除，处理较为复杂，这里我们设置一个哨兵NewHead，让NewHead.next = head,然后从哨兵开始遍历，最后返回NewHead.next就可以完美解决！
3、删除的位置是中间部分，就正常p.next = p.next.next，删除节点。
情况1和情况三可以整合，然后再加个哨兵，就可以统一三种情况。实现如下
C
#include<stdio.h> #include<stdlib.h> typedef struct ListNode { int m_nValue; struct ListNode* m_pNext; }ListNode; ListNode* CreateEndLinkList()//尾插法创建单链表 { ListNode* head = NULL; ListNode* q = NULL; ListNode* p = NULL; head = (ListNode*)malloc(sizeof(ListNode));//申请头节点空间 q = head; if (NULL == head) { perror("申请空间失败"); exit(EXIT_FAILURE); } head->m_nValue = 0; head->m_pNext = NULL; int num = 10; int size = 5; while (size > 0) { p = (ListNode*)malloc(sizeof(ListNode));//申请子节点空间 p->m_nValue = num++; p->m_pNext = NULL;//尾插入 q->m_pNext = p; q = p; size--; } return head; } void PrintLinkList(ListNode* head)//输出链表数据 { ListNode* p = head->m_pNext; printf("head->"); while (NULL != p) { printf("%d->", p->m_nValue); p = p->m_pNext; } printf("NULL\n"); } ListNode* DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)//删除链表的节点 { if (*pListHead == NULL || pToBeDeleted == NULL) { return *pListHead; } ListNode* NewHead = (ListNode*)malloc(sizeof(ListNode)); if (NULL == NewHead) { perror("申请空间失败\n"); } NewHead->m_pNext = *pListHead;//创建新的一个假头，防止头节点被删除 ListNode* p = NewHead; //不能走到空 或者找到目标节点 while (p->m_pNext != NULL && p->m_pNext != pToBeDeleted) { p = p->m_pNext; } //防止要删除的节点不在pListHead链表中 if (p->m_pNext != NULL && p->m_pNext == pToBeDeleted) { ListNode* tmp = p->m_pNext; p->m_pNext = p->m_pNext->m_pNext; free(tmp); tmp = NULL; } return NewHead->m_pNext; } int main() { ListNode* head = CreateEndLinkList();//10 11 12 13 14 PrintLinkList(head); ListNode* p = head->m_pNext->m_pNext->m_pNext;//指向12 //因为设计的链表头部不存储数据，所以从头下面一个开始 PrintLinkList(DeleteNode(&head->m_pNext, p));//删除12 return 0; }
但是时间复杂度位O(n);不满足要求，因为链表只能从前到后遍历，所哟时间复杂度必然是O(n);所以跳出常规思维，能否从要删除的节点本身来解决。
披着羊皮的狼 - 替罪法
因为我们不知道要删除的节点的前一个节点，所以我们不能删除目标节点A，但是可以让B把所有信息给A，然后把B删除掉。细思极恐啊。
我们删除的不是A，而是A下面的节点B，现在的节点B实际是披着羊皮的狼。
这里有三种情况：
1、删除节点在最后，没有“替罪羊”。就只能用开始的线性遍历解决。
2、删除节点在开头，直接删除当前节点。
3、删除节点在中间，就用上述的替罪法
*时间复杂度为((n-1)O(1) + O(n))/n 等于O(1);空间复杂度O(1);满足要求
C
#include<stdio.h> #include<stdlib.h> typedef struct ListNode { int m_nValue; struct ListNode* m_pNext; }ListNode; ListNode* CreateEndLinkList()//尾插法创建单链表 { ListNode* head = NULL; ListNode* q = NULL; ListNode* p = NULL; head = (ListNode*)malloc(sizeof(ListNode));//申请头节点空间 q = head; if (NULL == head) { perror("申请空间失败"); exit(EXIT_FAILURE); } head->m_nValue = 0; head->m_pNext = NULL; int num = 10; int size = 5; while (size > 0) { p = (ListNode*)malloc(sizeof(ListNode));//申请子节点空间 if (NULL == p) { perror("申请空间失败！\n"); exit(EXIT_FAILURE); } p->m_nValue = num++; p->m_pNext = NULL;//尾插入 q->m_pNext = p; q = p; size--; } return head; } void PrintLinkList(ListNode* head)//输出链表数据 { ListNode* p = head; printf("head->"); while (NULL != p) { printf("%d->", p->m_nValue); p = p->m_pNext; } printf("NULL\n"); } ListNode* DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)//删除链表的节点 { if (*pListHead == NULL || pToBeDeleted == NULL) { return *pListHead; } if (pToBeDeleted->m_pNext != NULL)//情况三 { ListNode* tmp = pToBeDeleted->m_pNext; pToBeDeleted->m_nValue = tmp->m_nValue; pToBeDeleted->m_pNext = tmp->m_pNext; free(tmp); tmp = NULL; return *pListHead; } else if (*pListHead == pToBeDeleted)//情况一 { free(pToBeDeleted); return (*pListHead)->m_pNext; } else//情况二 { ListNode* p = *pListHead; //不能走到空 或者找到目标节点 while (p->m_pNext != NULL && p->m_pNext != pToBeDeleted) { p = p->m_pNext; } //防止要删除的节点不在pListHead链表中 if (p->m_pNext != NULL && p->m_pNext == pToBeDeleted) { ListNode* tmp = p->m_pNext; p->m_pNext = p->m_pNext->m_pNext; free(tmp); tmp = NULL; } return *pListHead; } return *pListHead; } int main() { ListNode* head = CreateEndLinkList();//10 11 12 13 14 PrintLinkList(head->m_pNext); ListNode* p = head->m_pNext->m_pNext->m_pNext;//指向12 //因为设计的链表头部不存储数据，所以从头下面一个开始 PrintLinkList(DeleteNode(&head->m_pNext, p));//删除12 return 0; }
测试删除头部
测试删除尾部
测试删除中间
本章完1
