面试题11：在O(1)时间删除链表结点
方法一：顺序查找要删除的结点，并在链表中删除。时间复杂度为O(n),不满足题目要求
代码：
void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted)
{
if (*pListHead != NULL && pToBeDeleted != NULL)
{
if (*pListHead == pToBeDeleted)
{
*pListHead = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
else
{
ListNode *pCur = *pListHead;
while (pCur->m_pNext != pToBeDeleted)
{
pCur = pCur->m_pNext;
}
pCur->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
else
{
cout << "链表为空！" << endl;
}
}
void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted)
{
if (*pListHead != NULL && pToBeDeleted != NULL)
{
if (*pListHead == pToBeDeleted)
{
*pListHead = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
else
{
ListNode *pCur = *pListHead;
while (pCur->m_pNext != pToBeDeleted)
{
pCur = pCur->m_pNext;
}
pCur->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
else
{
cout << "链表为空！" << endl;
}
}
方法二：把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，相当于把当前要删除的结点删除了，不需要从前向后扫描链表。
注意：考虑特殊情况：被删除的结点是尾结点
两种情况：1. 链表有多个结点（只能顺序查找）； 2. 链表只有一个结点
代码：
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode *m_pNext;
};
//删除指定结点
void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted)
{
if (*pListHead!=NULL && pToBeDeleted!=NULL)
{
if (pToBeDeleted->m_pNext != NULL)//被删除的结点不是尾结点
{
ListNode *pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;
delete pNext;
pNext = NULL;
}
else if (*pListHead == pToBeDeleted)//链表中只有一个结点
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
}
else//被删除的结点是尾结点
{
ListNode *pCur = *pListHead;
while (pCur->m_pNext != pToBeDeleted)
{
pCur = pCur->m_pNext;
}
pCur->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
else
{
cout << "链表为空！" << endl;
}
}
//创建一个链表，输入从头到尾结点的值，输入-1表示结束
void CreateList(ListNode *& pHead)
{
ListNode *pListNode = NULL;
ListNode *pCurLastNode = NULL;
bool isHead = true;
while (1)
{
if (isHead)
{
pHead = new ListNode();
cin >> pHead->m_nValue;
pHead->m_pNext = NULL;
isHead = false;
pCurLastNode = pHead;
}
else
{
pListNode = new ListNode();
cin >> pListNode->m_nValue;
if (pListNode->m_nValue == -1)
{
break;
}
pListNode->m_pNext = NULL;
pCurLastNode->m_pNext = pListNode;
pCurLastNode = pListNode;
}
}
}
//从头到尾打印链表
void PrintList(ListNode *pHead)
{
if (pHead != NULL)
{
ListNode *pCur = pHead;
while (pCur != NULL)
{
cout << pCur->m_nValue << " ";
pCur = pCur->m_pNext;
}
cout << endl;
}
else
{
cout << "链表为空！" << endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode *pHead = NULL;
//创建链表
CreateList(pHead);
PrintList(pHead);
//删除头结点
DeleteNode(&pHead, pHead);
PrintList(pHead);
//删除第二个结点
if (pHead != NULL)
{
DeleteNode(&pHead, pHead->m_pNext);
PrintList(pHead);
}
//删除尾结点
ListNode *pCur = pHead;
if (pCur != NULL)
{
while (pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
}
DeleteNode(&pHead, pCur);
PrintList(pHead);
}
system("pause");
return 0;
}
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode *m_pNext;
};
//删除指定结点
void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted)
{
if (*pListHead!=NULL && pToBeDeleted!=NULL)
{
if (pToBeDeleted->m_pNext != NULL)//被删除的结点不是尾结点
{
ListNode *pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;
delete pNext;
pNext = NULL;
}
else if (*pListHead == pToBeDeleted)//链表中只有一个结点
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
}
else//被删除的结点是尾结点
{
ListNode *pCur = *pListHead;
while (pCur->m_pNext != pToBeDeleted)
{
pCur = pCur->m_pNext;
}
pCur->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
else
{
cout << "链表为空！" << endl;
}
}
//创建一个链表，输入从头到尾结点的值，输入-1表示结束
void CreateList(ListNode *& pHead)
{
ListNode *pListNode = NULL;
ListNode *pCurLastNode = NULL;
bool isHead = true;
while (1)
{
if (isHead)
{
pHead = new ListNode();
cin >> pHead->m_nValue;
pHead->m_pNext = NULL;
isHead = false;
pCurLastNode = pHead;
}
else
{
pListNode = new ListNode();
cin >> pListNode->m_nValue;
if (pListNode->m_nValue == -1)
{
break;
}
pListNode->m_pNext = NULL;
pCurLastNode->m_pNext = pListNode;
pCurLastNode = pListNode;
}
}
}
//从头到尾打印链表
void PrintList(ListNode *pHead)
{
if (pHead != NULL)
{
ListNode *pCur = pHead;
while (pCur != NULL)
{
cout << pCur->m_nValue << " ";
pCur = pCur->m_pNext;
}
cout << endl;
}
else
{
cout << "链表为空！" << endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode *pHead = NULL;
//创建链表
CreateList(pHead);
PrintList(pHead);
//删除头结点
DeleteNode(&pHead, pHead);
PrintList(pHead);
//删除第二个结点
if (pHead != NULL)
{
DeleteNode(&pHead, pHead->m_pNext);
PrintList(pHead);
}
//删除尾结点
ListNode *pCur = pHead;
if (pCur != NULL)
{
while (pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
}
DeleteNode(&pHead, pCur);
PrintList(pHead);
}
system("pause");
return 0;
}
补充：软件开发 , C++ ,
