【6】单链表【插入，删除，逆序打印】完整代码

约定不等于承诺〃 2022-05-27 06:59 163阅读 0赞

## 面试题6：链表的插入，删除某一结点，从尾到头打印链表 ##

### 【0】目录： ###

**【1】题目**  
**【2】分析**  
**【3】完整代码及测试用例**  
**【4】测试结果**

### **【1】题目：** ###

（1）输入一个链表的头结点，从尾到头反过来打印出每个结点的值。  
（2）实现单链表的插入，  
（3）实现单链表删除某一指定数字（第一次出现的位置）

### **【2】分析：**  ###

**（1）第一题分析：**  
（1）逆向打印单链表，从前向后遍历此单链表，先遍历的结点后打印，最后遍历的结点最先打印，我们首先想到的应该时是栈这种结构，所以第一种解决方案就是利用栈实现，只要链表不为空，就循环遍历每一个结点，每次访问到一个结点，便让其入栈，那么，链表最后一个入栈的元素就在栈的顶端，打印顶端元素，再让栈顶元素出栈即可

void PrintListReverse(ListNode*pHead )
    {
        std::stack<ListNode*> nodes;
        if(pHead == NULL)
        {
            return ;
        }
        ListNode* pNode = pHead;
        while( pNode != NULL )
        {
            nodes.push(pNode);
            pNode = pNode->_pNext;
        }
        while(!nodes.empty())
        {
            pNode = nodes.top();
            printf( "%d\t", pNode->_value );
    
            nodes.pop();
        }
    }

（2）递归实现：我们知道，递归的底层，本来就是栈实现的，所以这里我们也可以利用递归；

void  PrintListReverse2(ListNode*pHead )
    {
    
        if(pHead == NULL)
        {
            return ;
        }
        ListNode* pNode = pHead;
        if(pNode!= NULL)
        {
            if(pNode ->_pNext !=NULL)
            {
                PrintListReverse2(pNode->_pNext);
            }
            printf( "%d\t", pNode->_value );
        }
    }

**【2】第二题分析：**实现单链表的插入，我们总共分为两种情况：  
（1）链表为空链表  
（2）链表为非空链表

void addToTail(ListNode** pHead,int value)
    {
        ListNode* pNew = new ListNode();
        pNew->_pNext = NULL;
        pNew ->_value = value;
    
        if(*pHead == NULL)//空链表
        {
            *pHead = pNew;
        }
        else{
                ListNode* pNode = *pHead;//非空链表
                while(pNode->_pNext !=NULL)
                {
                    pNode = pNode ->_pNext;
                }
                pNode ->_pNext = pNew;
            }
    }

**【3】第三题分析：**  
在链表中找到第一个含有某值的结点并删除该节点，分两种情况：  
（1）删除的为头结点  
（2）删除的非头节点

void RemoveNode(ListNode** pHead, int value)
    {
        if(pHead == NULL||*pHead == NULL)
        {
            printf("参数传递错误，无法删除\n");
            return ;
        }
        ListNode* pBeDeleted = NULL;
        if((*pHead)->_value == value )
        {
            pBeDeleted = *pHead;
            *pHead =(*pHead)->_pNext; 
        }
        else
        {
            ListNode* pNode = *pHead;
            while(pNode->_pNext != NULL&&pNode->_pNext->_value != value)
            {
                pNode = pNode->_pNext;
            }
            if(pNode->_pNext != NULL &&pNode->_pNext->_value == value )
            {
                pBeDeleted = pNode->_pNext;
                pNode->_pNext = pNode->_pNext ->_pNext;
            }
            if(pBeDeleted != NULL )
            {
                delete pBeDeleted;
                pBeDeleted = NULL;
            }
        }
    }

### **3.完整代码及测试** ###

#include<iostream>
    using namespace std;
    #include<cstdio>
    #include<stack>
    struct ListNode
    {
        int _value;
        struct ListNode* _pNext;
    }PNode;
    
    ListNode* BuyNode(int data)   //创建新的结点
    {
        ListNode *pNewNode = (ListNode*)malloc(sizeof(ListNode));
        if(NULL != pNewNode)
        {
            pNewNode->_value = data;
            pNewNode->_pNext = NULL;
        }
        return pNewNode;
    }
    
    void pushback(ListNode** pNode,int value)//实现单链表尾插
    {
        if(*pNode == NULL)
            {
                *pNode = BuyNode(value);
                return ;
            }
        ListNode* Cur = *pNode;
         while ((*pNode)->_pNext != NULL)
            {
                (*pNode) = (*pNode)->_pNext;
            }
            (*pNode)->_pNext = BuyNode(value);
            *pNode = Cur;
    }
    
    
    void Distroy(ListNode*root)//实现单链表销毁
    {
        if(root == NULL )
        {
            return ;
        }
        Distroy(root->_pNext);
        free(root);
        root = NULL;
    }
    void Print(ListNode* pNode)//实现单链表打印
    {
        while (pNode!= NULL)
        {
            cout << pNode->_value << " ";
            pNode = pNode->_pNext;
        }
        cout << endl;
    }
    //=====================从头到尾逆向打印单链表===============
    //********************************************1.栈实现******
    //==========================================================
    void PrintListReverse(ListNode*pHead )
    {
        std::stack<ListNode*> nodes;
        if(pHead == NULL)
        {
            return ;
        }
        ListNode* pNode = pHead;
        while( pNode != NULL )
        {
            nodes.push(pNode);
            pNode = pNode->_pNext;
        }
        while(!nodes.empty())
        {
            pNode = nodes.top();
            printf( "%d\t", pNode->_value );
    
            nodes.pop();
        }
    }
    
    //=====================从头到尾逆向打印单链表===============
    //***************************************2.递归实现*********
    //==========================================================
    void  PrintListReverse2(ListNode*pHead )
    {
    
        if(pHead == NULL)
        {
            return ;
        }
        ListNode* pNode = pHead;
        if(pNode!= NULL)
        {
            if(pNode ->_pNext !=NULL)
            {
                PrintListReverse2(pNode->_pNext);
            }
            printf( "%d\t", pNode->_value );
        }
    }
    
    //=====================单链表插入===========================
    //**********************************************************
    //==========================================================
    void addToTail(ListNode** pHead,int value)
    {
        ListNode* pNew = new ListNode();
        pNew->_pNext = NULL;
        pNew ->_value = value;
    
        if(*pHead == NULL)//空链表
        {
            *pHead = pNew;
        }
        else{
                ListNode* pNode = *pHead;//非空链表
                while(pNode->_pNext !=NULL)
                {
                    pNode = pNode ->_pNext;
                }
                pNode ->_pNext = pNew;
            }
    }
    
    //=====================单链表删除值为value的节点============
    //**********************************************************
    //==========================================================
    void RemoveNode(ListNode** pHead, int value)
    {
        if(pHead == NULL||*pHead == NULL)
        {
            printf("参数传递错误，无法删除\n");
            return ;
        }
        ListNode* pBeDeleted = NULL;
        if((*pHead)->_value == value )
        {
            pBeDeleted = *pHead;
            *pHead =(*pHead)->_pNext; 
        }
        else
        {
            ListNode* pNode = *pHead;
            while(pNode->_pNext != NULL&&pNode->_pNext->_value != value)
            {
                pNode = pNode->_pNext;
            }
            if(pNode->_pNext != NULL &&pNode->_pNext->_value == value )
            {
                pBeDeleted = pNode->_pNext;
                pNode->_pNext = pNode->_pNext ->_pNext;
            }
            if(pBeDeleted != NULL )
            {
                delete pBeDeleted;
                pBeDeleted = NULL;
            }
        }
    }
    
    
    // ====================测试代码====================
    
    //===============逆向打印单链表========================================
    //*********************************************************************
    //=====================================================================
    void Test(ListNode* pHead)
    {
        printf("栈实现逆向打印： ");
        PrintListReverse(pHead);
        printf("\n");
        printf("递归实现逆向打印：");
        PrintListReverse2(pHead);
    }
    
    // ===========1->2->3->4->5=================
    void Test1()
    {
        printf("\nTest1 begins.\n");
        ListNode* pNode = NULL;
           pushback(&pNode, 1);
           pushback(&pNode, 2);
           pushback(&pNode, 3);
           pushback(&pNode, 4);
           pushback(&pNode, 5);
        Test(pNode);
        Distroy(pNode);
    }
    
    // 只有一个结点的链表: 1
    void Test2()
    {
        printf("\nTest2 begins.\n");
    
        ListNode* pNode1 = BuyNode(1);
    
        Test(pNode1);
    
        Distroy(pNode1);
    }
    
    // 空链表
    void Test3()
    {
        printf("\nTest3 begins.\n");
    
        Test(nullptr);
    }
    //===============实现单链表的插入======================================
    //*********************************************************************
    //=====================================================================
    
    //===========链表非空，实现尾插========
    void test4()
    {
    
          ListNode* pNode = NULL;
           pushback(&pNode, 5);
           pushback(&pNode, 6);
           pushback(&pNode, 7);
           pushback(&pNode, 8);
           printf("插入之前打印:\n");
           Print(pNode);
    
           addToTail(&pNode,99);
           printf("插入之后打印:\n");
           Print(pNode);
    }
    //=============链表为空，实现插入========
    void test5()
    {
    
          ListNode* pNode = NULL;
    
           printf("插入之前打印:\n");
           Print(pNode);
    
           addToTail(&pNode,99);
           printf("插入之后打印:\n");
           Print(pNode);
    }
    //===============删除某个数字在链表中第一次出现的节点==================
    //*********************************************************************
    //=====================================================================
    void test6()//删除的数字非头节点
    {
        ListNode* pNode = NULL;
           pushback(&pNode, 1);
           pushback(&pNode, 2);
           pushback(&pNode, 3);
           pushback(&pNode, 4);
           pushback(&pNode, 3);
           printf("删除之前打印单链表：");
           Print(pNode);
    
           RemoveNode(&pNode, 3);
    
           printf("删除之后打印单链表：");
           Print(pNode);
    }
    
    void test7()//删除的数字为头节点
    {
        ListNode* pNode = NULL;
           pushback(&pNode, 55);
           pushback(&pNode, 66);
           pushback(&pNode, 77);
           pushback(&pNode, 88);
           pushback(&pNode, 99);
           printf("删除之前打印单链表：");
           Print(pNode);
    
           RemoveNode(&pNode, 55);
    
           printf("删除之后打印单链表：");
           Print(pNode);
    }
    void test8()//链表为空
    {
        ListNode* pNode = NULL;
           printf("删除之前打印单链表：null");
           Print(pNode);
    
           RemoveNode(&pNode, 333);
    
           printf("删除之后打印单链表：");
           Print(pNode);
    }
    
    
    int main()
    {
        Test1();
        Test2();
        Test3();
        test4();
        test5();
        test6();
        test7();
        test8();
        return 0;
    }

### **4.测试结果如下：** ###

![这里写图片描述][70]

[70]: /images/20220527/2bfc9cad57244d48b367c91053323031.png