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

缺乏、安全感 2022-06-17 01:16 143阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。链表结点定义如下：struct&nbsp;ListNode{
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m_nKey;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ListNode*&nbsp;m_pNext;};详细描述：本题为考察链表的插入和删除知识。链表的值不能重复构造过程，例如1&nbsp;-&gt;&nbsp;23&nbsp;-&gt;&nbsp;25&nbsp;-&gt;&nbsp;14&nbsp;-&gt;&nbsp;57&nbsp;-&gt;&nbsp;2最后的链表的顺序为&nbsp;2&nbsp;7&nbsp;3&nbsp;1&nbsp;5&nbsp;4&nbsp;删除&nbsp;结点&nbsp;2&nbsp;则结果为&nbsp;7&nbsp;3&nbsp;1&nbsp;5&nbsp;4&nbsp;&nbsp;&nbsp;</pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 链表,指针,结构体</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 1&nbsp;输入链表结点个数 2&nbsp;输入头结点的值 3&nbsp;按照格式插入各个结点 4&nbsp;输入要删除的结点的值 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输出删除结点后的序列 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 5 2 3 2 4 3 5 2 1 4 3</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 2 1 5 4</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <string> 
 #include <vector>
 #include <algorithm>
 //#include "Customer.h"
 using namespace std;
 
 struct ListNode
 {
 	int m_nKey;
 	ListNode *m_pNext;
 };
 
 ListNode *head = NULL;
 
 ListNode* findNode(int value)
 {
 	ListNode *p = head;
 	while (p != NULL)
 	{
 		if (p->m_nKey == value)
 			return p;
 		p = p->m_pNext;
 	}
 	return NULL;
 }
 
 void insertNode(int cur, int pre)
 {
 	ListNode *p = (ListNode*)malloc(sizeof(ListNode));
 	p->m_nKey = cur;
 	p->m_pNext = NULL;
 	if (head == NULL)
 	{
 		ListNode *preNode = (ListNode*)malloc(sizeof(ListNode));
 		preNode->m_nKey = pre;
 		preNode->m_pNext = p;
 		head = preNode;
 		return;
 	}
 	else
 	{
 		ListNode *preNode = findNode(pre);
 		p->m_pNext = preNode->m_pNext;
 		preNode->m_pNext = p;
 	}
 }
 
 void deleteNode(int value)
 {
 	ListNode *pre = NULL;
 	ListNode *cur = head;
 	while (cur!=NULL)
 	{
 		if (pre == NULL && cur->m_nKey == value)
 		{
 			pre = head;
 			cur = cur->m_pNext;
 			free(pre);
 			pre = NULL;
 			head = cur;
 			continue;
 		}
 		if (cur->m_nKey == value)
 		{
 			pre->m_pNext = cur->m_pNext;
 			free(cur);
 			cur = pre->m_pNext;
 		}
 		else
 		{
 			pre = cur;
 			cur = cur->m_pNext;
 		}	
 	}
 }
 int main()
 {
 	int countNode;
 	cin >> countNode;
 
 	head = (ListNode*)malloc(sizeof(ListNode));
 	cin>>head->m_nKey;
 	head->m_pNext = NULL;
 
 	int cur, pre;
 	for (int i = 0; i < countNode-1; i++)
 	{
 		cin >> cur >> pre;
 		insertNode(cur, pre);
 	}
 
 	int deleteValue;
 	cin >> deleteValue;
 	deleteNode(deleteValue);
 
 	while (head != NULL)
 	{
 		cout << head->m_nKey << endl;
 		head = head->m_pNext;
 	}
 	return 0;
 }