面試題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;
}