从单向链表中删除指定值的节点

题目描述

输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。

链表结点定义如下：

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 输入要删除的结点的值

输出描述:

输出删除结点后的序列

输入例子:

2 1 5 4

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct ListNode
 6 {
 7     int m_nKey;
 8     ListNode *m_pNext;
 9 };
10 
11 int main()
12 {
13     int num;
14     while (cin >> num)
15     {
16         int value,value1,value2;
17         cin >> value;
18         ListNode * head = (ListNode*)malloc(sizeof(ListNode));
19         head->m_nKey = value;
20         head->m_pNext = NULL;
21         ListNode *p=NULL;
22 
23         for (int i = 1; i < num; i++)
24         {
25             cin >> value1 >> value2;
26             p = head;
27 
28             while (p->m_nKey != value2)
29             {
30                 p = p->m_pNext;
31             }
32             if (p->m_pNext == NULL)
33             {
34                 ListNode *q = (ListNode*)malloc(sizeof(ListNode));
35                 q->m_nKey = value1;
36                 q->m_pNext = NULL;
37                 p->m_pNext = q;
38             }
39             else
40             {
41                 ListNode *q = new ListNode();
42                 q->m_nKey = value1;
43                 q->m_pNext = p->m_pNext;
44                 p->m_pNext = q;
45             }
46             
47         }
48 
49         int del_value;
50         cin >> del_value;
51         p = head;
52         if (p->m_nKey == del_value)
53         {
54             head = p->m_pNext;
55         }
56         while (p->m_pNext != NULL)
57         {
58             if (p->m_pNext->m_nKey == del_value)
59             {
60                 p->m_pNext = p->m_pNext->m_pNext;
61                 break;
62             }
63             else
64             {
65                 p = p->m_pNext;
66             }
67         }
68 
69         p = head;
70         while (p != NULL)
71         {
72             cout << p->m_nKey <<' ';
73             p = p->m_pNext;
74         }
75         cout << endl;
76     }
77     
78     
79     
80     return 0;
81 }