华为机试题：删除链表中的重复节点、剩余节点逆序输出

喜欢ヅ旅行 2022-08-20 07:16 41阅读 0赞

<table style="margin:0px; padding:0px; width:970px; border:0px; border-collapse:collapse; border-spacing:0px; empty-cells:show; color:rgb(0,0,0); font-family:'Times New Roman',Arial,微软雅黑,宋体,Tahoma,Helvetica,SimSun,sans-serif,宋体"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 描述:&nbsp;</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 题目描述： 输入一个不带头节点的单向链表(链表的节点数小于100),删除链表中内容重复的节点（重复的节点全部删除），剩余的节点逆序倒排。 要求实现函数：&nbsp; void&nbsp;vChanProcess(strNode&nbsp;*&nbsp;pstrIn,strNode&nbsp;*&nbsp;pstrOut); 【输入】&nbsp;pstrIn：输入一个不带头节点的单向链表 【输出】&nbsp;pstrOut：删除内容重复的节点（重复的节点全部删除），剩余节点逆序输出(不带头节点,链表第一个节点的内存已经申请)。 【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出 示例&nbsp; 输入链表的内容依次为&nbsp;6,7,8,8,9,10,6 则输出链表的内容依次应该是&nbsp;10,9,7 &nbsp; &nbsp;</td> 
 </tr> 
 </tbody> 
</table>

#include <stdlib.h>
 #include <vector>
 #include <algorithm>
 #include <iostream>
 #include <map>
 #include "oj.h"
 
 using namespace std;
 
 /*
 功能: 输入一个不带头节点的单向链表(链表的节点数小于100),删除链表中内容重复的节点（重复的节点全部删除），剩余的节点逆序倒排。
 
 输入: pstrIn： 输入一个不带头节点的单向链表
 
 输出: pstrOut：删除内容重复的节点后，逆序排列的链表(不带头节点,链表第一个节点的内存已经申请)。
 
 返回:
 
 示例:
 输入链表的内容依次为 6,7,8,8,9,10,6
 则输出链表的内容依次应该是 10,9,7
 
 */
 
 
 int iChanProcess(strNode * pstrIn,strNode * pstrOut)
 {
 	if (pstrIn == NULL)
 	{
 		return 0;
 	}
 	vector<int> vec;
 	map<int, int> mmap;
 	strNode *p = pstrIn;
 	int i = 0;
 
 	/*把所有的值取出来*/
 	while (p)
 	{
 		mmap[p->data]++;
 		p = p->pstrNext;
 
 		
 	}
 	/*把没有重复的值取出来*/
 	map<int, int>::iterator it;
 	for (it = mmap.begin(); it != mmap.end(); it++)
 	{
 		if (it->second == 1)
 		{
 			vec.push_back(it->first);
 		}
 	}
 
 	if (vec.empty())
 	{
 		return 0;
 	}
 
 	/*排序*/
 	sort(vec.begin(), vec.end());
 
 
 	pstrOut->data = vec[vec.size() - 1];
 	pstrOut->pstrNext = NULL;
 
 	strNode *pCurrNode = pstrOut;
 	for (i = vec.size() - 2; i >= 0; i--)
 	{
 		strNode *pNode = (strNode *)malloc(sizeof(strNode));
 		pNode->data = vec[i];
 		pNode->pstrNext = NULL;
 
 		pCurrNode->pstrNext = pNode;
 		pCurrNode = pNode;
 	}
 
 	return 0;
 }
 
 /* 释放链表 */
 void vFreeChan(strNode * pstrChan)
 {
 	strNode *pnext = NULL, *p = NULL;
 	p = pstrChan;
 	while (p)
 	{
 		/*指向下一个节点*/
 		pnext = p->pstrNext;
 		free(p);
 		p = pnext;
 	}
 
 	return;
 }