[编程题]从单向链表中删除指定值的节点

r囧r小猫 2022-07-13 04:41 120阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。  
链表结点定义如下：  
  
struct ListNode  
  
\{  
int m\_nKey;  
  
ListNode\* m\_pNext;  
  
\};  
  
详细描述：  
本题为考察链表的插入和删除知识。  
  
链表的值不能重复  
  
构造过程，例如  
  
1 -> 2  
3 -> 2  
  
5 -> 1  
4 -> 5  
  
7 -> 2  
最后的链表的顺序为 2 7 3 1 5 4  
  
删除 结点 2  
  
则结果为 7 3 1 5 4

**输入描述：**

1 输入链表结点个数
    2 输入头结点的值
    3 按照格式插入各个结点
    4 输入要删除的结点的值

**输出描述：**

> 输出删除结点后的序列

**输入例子：**

5
    2
    3 2
    4 3
    5 2
    1 4
    3

**输出例子：**

> 2 5 4 1

### 二、问题分析 ###

主要是对指针的应用，注意声明一个指针，比如int \*p，并没有给它所指向的int分配内存空间，只有当p = new int()之后才会给p指向的int分配内存空间，delete p; p = 0;是释放p所指向的内存空间，但是指针p依然指向已被释放的原来指向的内存空间，需要将p置位0，避免指针出错。

**解题方式1：**

这个是正确解。

#include<iostream>
    using namespace std;
    struct ListNode
    {
          int  val;
          ListNode* next;
    };
    int main(){
        int n,head_value;
        while(cin>>n>>head_value){
            ListNode *p,*q,*head=new ListNode;
            head->val=head_value;
            head->next=NULL;
            q=head;
            for(int i=0;i<n-1;i++){
                int x,y;
                cin>>x>>y;
                p=new ListNode;
                p->val=x;
                p->next=NULL;
                while(q){
                    if(q->val==y){
                          p->next=q->next;
                        q->next=p;
                        break;
                    }else
                        q=q->next;
                }
                q=head;
            }
            int denum;
            cin>>denum;
            q=head;
            while(q){
                if(q->val==denum){
                    if(q==head){
                        head=q->next;
                        delete q;
                    }else{
                        p->next=q->next;
                        delete q;
                    }
                    break;
                }else{
                     p=q;
                     q=q->next;
                }  
            }
            q=head;
            while(q){
                cout<<q->val<<' ';
                q=q->next;
            }
            cout<<endl;
        }
        return 0;
    }

**解题方式2：**

这是我自己写的方法，不明白为什么同一个测试用例，在牛客网OJ上运行出错，我在子集的电脑上运行却没有错误。

#include <iostream>
    using namespace std;
    
    struct ListNode
    {
        int m_key;
        ListNode *m_next;
    };
    
    int main()
    {
        int n;
        while (cin >> n)
        {
            ListNode *list = new ListNode();
            int head;
            cin >> head;
            list->m_key = head;
            list->m_next = NULL;
            n--;
            int back, pre;
            ListNode *p = 0;
            while (n--)
            {
                cin >> back >> pre;
                p = list;
                while (p != NULL)
                {
                    if (p->m_key == pre)
                    {
                        ListNode *temp = new ListNode();
                        temp->m_key = back;
                        temp->m_next = p->m_next;
                        p->m_next = temp;
                        break;
                    }
                    p = p->m_next;
                }
            }
            int del;
            cin >> del;
            p = list;
            ListNode *q = 0;
            if (p->m_next == NULL)
            {
                continue;
            } else {
                if (p->m_key == del)
                {
                    q = p;
                    p = p->m_next;  
                    delete q;
                    q = 0;
                }
            }
            while (p->m_next != NULL)
            {
                q = p->m_next;
                if (q->m_key == del)
                {
                    p->m_next = q->m_next;
                    delete q;
                    q = 0;
                    break;
                }
                p = q;
                q = q->m_next;
            }
            p = list;
            cout << p->m_key;
            p = p->m_next;
            while (p != NULL)
            {
                cout << " " << p->m_key;
                p = p->m_next;
            }
        }
    
        return 0;
    }