剑指offer—第三章高质量代码（o(1)时间删除链表节点）

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O（1）时间删除该节点，链表节点与函数的定义如下：struct ListNode{int m_nValue;ListNode* m_pValue;};void DeleteNode(ListNode** pListNode,ListNode * pToBeDeleted){}

思路：将要删除的节点的下一个节点的值赋值给i，删除下一个节点，但要考虑到删除的节点是最后一个节点并且该链表不止有一个节点的情况和该链表只有一个节点，该节点既是头节点也是尾节点的情况。

C++代码：

#include<iostream>

using namespace std;

struct ListNode

{

    int m_nValue;

    ListNode* m_pNext;

};

//创建链表

ListNode* CreateLink(int a[],int k)

{

    ListNode* Head=NULL,*q=NULL;

    for(int i=;i<k;i++)

    {

        ListNode * pNew=new ListNode();

        pNew->m_nValue=a[i];

        pNew->m_pNext=NULL;

        if(Head==NULL)

        {

            Head=pNew;

            q=pNew;

        }

        else

        {

            q->m_pNext=pNew;

            q=q->m_pNext;

        }  

    }

    return Head;

}

//从头到尾打印列表

void printLink(ListNode * pHead)

{

    ListNode *p=pHead;

    while(p)

    {

        cout<<p->m_nValue<<" ";

        p=p->m_pNext;

    }

    cout<<endl;

}

void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted)

{

    if(!pListHead||!pToBeDeleted)

    {

        return;

    }

    //要删除的节点后面有节点

    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;

    }

}

void main()  

{

    int a[]={,,};

    ListNode * Head=CreateLink(a,);

    printLink(Head);

    ListNode* pNode=Head;

    while(pNode->m_nValue!=a[]&&pNode)

        pNode=pNode->m_pNext;

    if(!pNode)

    {

        printf("不存在这样的节点");

    }

    else

        DeleteNode(&Head,pNode);

    printLink(Head);

    cout<<endl;

}

Java代码：

public class SingleLinkList {

    public  static class ListNode

    {

        public int m_nValue;

        public ListNode m_pNext;

    }

    //创建链表

    public  static ListNode CreateLink(int a[],int k)

    {

        ListNode Head=null,q=null;

        for(int i=0;i<k;i++)

        {

            ListNode  pNew=new ListNode();

            pNew.m_nValue=a[i];

            pNew.m_pNext=null;

            if(Head==null)

            {

                Head=pNew;

                q=pNew;

            }

            else

            {

                q.m_pNext=pNew;

                q=q.m_pNext;

            }  

        }

        return Head;

    }

    //从头到尾打印列表

    public static  void printLink(ListNode pHead)

    {

        ListNode p=pHead;

        while(p != null)

        {

            System.out.print(p.m_nValue+" ");

            p=p.m_pNext;

        }

        System.out.println("\n");

    }

    public static void DeleteNode(ListNode pListHead,ListNode pToBeDeleted)

    {

        if(pListHead==null||pToBeDeleted==null)

        {

            return;

        }

        //要删除的节点后面有节点

        if(pToBeDeleted.m_pNext!=null)

        {

            ListNode pNext=pToBeDeleted.m_pNext;

            pToBeDeleted.m_nValue=pNext.m_nValue;

            pToBeDeleted.m_pNext=pNext.m_pNext;

        }

        //要删除的节点是头结点，也是最后一个节点

        else if(pListHead==pToBeDeleted)

        {

            pToBeDeleted=null;

            pListHead=null;

        }

        else

        {

            ListNode pNode=pListHead;

            while(pNode.m_pNext!=pToBeDeleted)

            {

                pNode=pNode.m_pNext;

            }

            pNode.m_pNext=null;

            pToBeDeleted=null;

        }

    }

    public static void main(String[] args)  

    {

        int a[]={1,2,3};

        ListNode  Head=CreateLink(a,3);

        printLink(Head);

        ListNode pNode=Head;

        while(pNode.m_nValue!=a[1]&&pNode!=null)

            pNode=pNode.m_pNext;

        if(pNode==null)

        {

            System.out.println("不存在这样的节点");

        }

        else

            DeleteNode(Head,pNode);

        printLink(Head);

        System.out.println("\n");

    } 

}

巴特西

剑指offer—第三章高质量代码（o(1)时间删除链表节点）

最新文章

热门文章