华为机试题：向升序单向链表中插入一个节点

红太狼 2022-08-20 05:08 36阅读 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)"> 
 <ul style="margin:0px; padding:0px"> 
 <li style="margin:0px; padding:0px"> 输入一个升序单向链表和一个链表节点，向单向链表中按升序插入这个节点。 </li> 
 <li style="margin:0px; padding:0px"> 输入为空指针的情况视为异常，另外不考虑节点值相等的情况。 </li> 
 <li style="margin:0px; padding:0px"> 链表结点定义如下： </li> 
 <li style="margin:0px; padding:0px"> struct&nbsp;ListNode </li> 
 <li style="margin:0px; padding:0px"> { </li> 
 <li style="margin:0px; padding:0px"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m_nKey; </li> 
 <li style="margin:0px; padding:0px"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ListNode*&nbsp;m_pNext; </li> 
 <li style="margin:0px; padding:0px"> }; </li> 
 </ul> 详细描述： 
 <ul style="margin:0px; padding:0px"> 
 <li style="margin:0px; padding:0px"> 接口说明 </li> 
 </ul> 原型： ListNode*&nbsp;InsertNodeToList(ListNode*&nbsp;pListHead,&nbsp;ListNode*&nbsp;pInsertNode); 输入参数： &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ListNode*&nbsp;pListHead&nbsp;&nbsp;单向链表 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ListNode*&nbsp;pInsertNode&nbsp;新插入节点 输出参数（指针指向的内存区域保证有效）： &nbsp;&nbsp;&nbsp;&nbsp;ListNode*&nbsp;pListHead&nbsp;&nbsp;单向链表 返回值： &nbsp;&nbsp;&nbsp;&nbsp;正常插入节点返回链表头指针，其它异常返回空指针 &nbsp; &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

#include "OJ.h"
 
 /*
 功能: 输入一个升序单向链表和一个链表节点，向单向链表中按升序插入这个节点。
 输入为空指针的情况视为异常，另外不考虑节点值相等的情况。
 
 输入: ListNode* pListHead 单向链表
 ListNode* pInsertNode 新插入节点
 
 输出: ListNode* pListHead 单向链表
 
 返回: 正常插入节点返回链表头指针，其它异常返回空指针
 */
 ListNode* InsertNodeToList(ListNode* pListHead, ListNode* pInsertNode)
 {
 	/*在这里实现功能*/
 	if (pListHead == NULL || pInsertNode == NULL)
 	{
 		return (ListNode*)NULL;
 	}
 
 	ListNode *tmp = (ListNode*)NULL;
 
 	/*当只有一个节点的情况*/
 	if (pListHead->m_pNext == NULL)
 	{
 		if (pListHead->m_nKey < pInsertNode->m_nKey)
 		{
 			pListHead->m_pNext = pInsertNode;
 			pInsertNode->m_pNext = (ListNode*)NULL;
 		}
 		else
 		{
 			tmp = pListHead;
 			pListHead = pInsertNode;
 			pInsertNode->m_pNext = tmp;
 		}
 		return pListHead;
 	}
 
 	/*找到比当前节点大的第一个节点*/
 	ListNode *pre = pListHead;
 	ListNode *p = pre->m_pNext;
 
 	while (p)
 	{
 		if (p->m_nKey > pInsertNode->m_nKey)
 		{
 			break;
 		}
 		pre = p;
 		p = pre->m_pNext;
 	}
 
 	/*当没有找到，就把整个节点插入到尾节点*/
 	if (p == NULL)
 	{
 		pre->m_pNext = pInsertNode;
 		pInsertNode->m_pNext = (ListNode*)NULL;
 	}
 	else //插入到p和pre中间
 	{
 		pre->m_pNext = pInsertNode;
 		pInsertNode->m_pNext = p;
 	}
 
 	return pListHead;
 }