学步园

60.在 O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。
链表结点的定义如下：
struct ListNode
{
int  m_nKey;
ListNode* m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead,  ListNode* pToBeDeleted);

分别处理头、尾、中间三个部分；

时间复杂度为（    O(1)  * （n-1） +   O(n)  ）/ n = O（1）

/*
60.在 O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。
链表结点的定义如下：
struct ListNode
{
	int  m_nKey;
	ListNode* m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead,  ListNode* pToBeDeleted);

思想很简单 ：
链表只知道后面一个 不知道前面一个 让要删除的等于后面一个 然后删除后一个 
但是要考虑 是尾节点 只有遍历了 

一个链表A->B->C->D->E->F->G。如果我们要删除结点E，
那么我们只需要让结点D的指针指向结点F即可，这需要顺序查找O(n)时间

现在只给出链表头结点的指针以及结点E的指针，而又是单项链表，
不能在O(1)时间内得到被删除结点前面的那一个结点的指针，

因此被删除结点E的后一个结点指针是很容易得到的，也就是E->m_pNext。
获得F的指针，将F的数据赋值给E，然后让E指向F的下一个结点。
这里虽然删除的是结点F，但是相当于删除的是结点E。并且是O(1)时间复杂度。 

*/
#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;

//链表结构
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};


//建立
ListNode *CreateList(int data[],int pos,int len)
{
	ListNode *list;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		list=(ListNode *)malloc(sizeof(ListNode));
		list->m_nValue=data[pos];
		list->m_pNext=CreateList(data,pos+1,len);
		return list;
	}
}

//遍历链表中的所有结点
void PrintList(ListNode* pHead)
{
    ListNode *pNode=pHead;
    while(pNode!=NULL)
    {
        cout<<pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;
    }
    cout<<endl;
}

void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted)
{
    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 *pNode=*pListHead;
        while(pNode->m_pNext!=pToBeDeleted)
            pNode=pNode->m_pNext;
        pNode->m_pNext=NULL;
        delete pToBeDeleted;
        pToBeDeleted=NULL;
    }
}

int main()
{
    
    int data[]={1,2,3,4,5,6,7,8};
    
    ListNode *list;
    list=CreateList(data,0,sizeof(data)/sizeof(int));//创建链表 1,2,3,4,5,6,7,8
    cout<<"原链表： "<<endl; 
	PrintList(list);//打印 1,2,3,4,5,6,7,8
    
    ListNode *delNode=list;
    //创建要删除的节点 删除5节点 
    while(delNode!=NULL)
    {
    	if (delNode->m_nValue==5)
    		break;
    	delNode=delNode->m_pNext;
    }
    //删除结点5
    DeleteNode(&list,delNode);
    cout<<"链表删除节点5之后： "<<endl; 
    PrintList(list);//打印
    
    
    ListNode *delNode2=list;
    //创建要删除的节点指向8 删除尾节点8节点 
    while(delNode2!=NULL)
    {
    	if (delNode2->m_nValue==8)
    		break;
    	delNode2=delNode2->m_pNext;
    }
    //删除结点
    DeleteNode(&list,delNode2);
    cout<<"链表接着删除尾节点8之后： "<<endl; 
    PrintList(list);//打印
}