《剑指offer》面试题13—O(1)时间删除链表结点

题目：给定单向链表的头指针和某结点指针，实现函数在O(1)时间内删除指定节点。

思路：由于没有要删除结点（j结点）的前一个结点（i结点）指针，通常想法是从头开始遍历找到指定结点的前一个结点（i结点），然后使i结点的指针指向j结点的后一个结点k结点。但是这样是O(n)的时间复杂度，不符合要求。

解决方法很巧妙：由于有要删除的j结点的指针，因此可以很容易得到j结点的后一个结点k结点的指针，只要把k结点的内容复制给i结点，然后删除k结点即可。

但是要注意！如果链表只有一个结点，head指针要指NULL；如果要删除的是尾结点，即后面没有结点了，那么也只能从头开始遍历。

 #include <iostream>

 using namespace std;

 class Node

 {

 public:

     Node(int v, Node* n)

     {val = v;

     next = n;}

     ~Node(){}

     int val;

     Node* next;

 };

 Node * phead = NULL;

 void AddNode(int val)

 {

     Node* pnode = new Node(val,NULL);

     //Node one_node(val,NULL); 这里有大bug！如果这样写，在函数退出时自动调用析构函数！链表就乱了！

     if(phead == NULL)

     {

         phead = pnode;

     }

     else

     {

         Node* p = phead;

         while(p->next != NULL)

         {

             p = p->next;

         }

         p->next = pnode;

     }

 }

 void PrintLink()

 {

     Node* p = phead;

     while(p != NULL)

     {

         int temp = p->val;

         cout<<temp<<endl;

         p = p->next;

     }

 }

 void DeleteNode(Node* pdelete)

 {

     Node * p;

     if(phead == NULL || pdelete == NULL)   //check

         return;

     if(pdelete == phead)  //the node to be deleted is equal to the head

     {

         if(phead->next == NULL)//only one node

         {

             delete pdelete;

             pdelete = NULL;

             phead = NULL;

         }

         else        //more than one node

         {

             phead = phead->next;

             delete pdelete;

             pdelete = NULL;

         }

     }

     else if(pdelete->next == NULL) //the node to be deleted is the last node

     {

         p = phead;

         while (p->next->next != NULL) p = p->next;  //find the node before the last node

         p->next = NULL;

         delete pdelete;

         pdelete = NULL;

     }

     else //the normal situation,not the head or the tail

     {

         Node* pnext = pdelete->next;

         pdelete->val = pnext->val;

         pdelete->next = pnext->next;

         delete pnext;

         pnext = NULL;

     }

 }

 int main()

 {

     int val,del,flag;

     Node* pdelete;

     cin>>val;

     while(val != )

     {

         AddNode(val);

         cin>>val;

     }

     PrintLink();

     cout<<"Input the node number you want to delete:"<<endl;

     cin>>del;

     pdelete = phead;

     if(phead == NULL) cout<<"No node!"<<endl;

     flag = ;

     for(int i=;i<del&&flag;i++)

     {

         if (pdelete->next!=NULL) pdelete = pdelete->next;

         else

         {

             cout << "The node not exists!"<<endl;

             flag=;

         }

     }

     if(flag) DeleteNode(pdelete);

     PrintLink();

     return ;

 }

巴特西

《剑指offer》面试题13—O(1)时间删除链表结点

最新文章

热门文章