[华为机试练习题]49.向升序单向链表中插入一个节点

题目

描述:

输入一个升序单向链表和一个链表节点，向单向链表中按升序插入这个节点。
输入为空指针的情况视为异常，另外不考虑节点值相等的情况。
链表结点定义如下：
struct ListNode
{
      int       m_nKey;
      ListNode* m_pNext;
};
详细描述：

接口说明
原型：

ListNode* InsertNodeToList(ListNode* pListHead, ListNode* pInsertNode);

输入参数：

 ListNode* pListHead  单向链表
 ListNode* pInsertNode 新插入节点

输出参数（指针指向的内存区域保证有效）：

ListNode* pListHead  单向链表

返回值：

正常插入节点返回链表头指针，其它异常返回空指针

练习阶段:

初级

代码

/*---------------------------------------
*   日期：2015-07-04
*   作者：SJF0115
*   题目：向升序单向链表中插入一个节点
*   来源：华为机试练习题
-----------------------------------------*/
#include <iostream>
#include "OJ.h"
using namespace std;

/*
功能:
    输入一个升序单向链表和一个链表节点，向单向链表中按升序插入这个节点
    输入为空指针的情况视为异常，另外不考虑节点值相等的情况。

输入:
    ListNode* pListHead  单向链表
    ListNode* pInsertNode 新插入节点

输出:
    ListNode* pListHead  单向链表

返回:
    正常插入节点返回链表头指针，其它异常返回空指针
*/
ListNode* InsertNodeToList(ListNode* pListHead, ListNode* pInsertNode){
    if(pListHead == NULL || pInsertNode == NULL){
        return NULL;
    }//if
    // 添加头结点
    ListNode* dummy = new ListNode();
    dummy->m_pNext = pListHead;

    ListNode* p = pListHead;
    ListNode* pre = dummy;
    while(p){
        // 插入
        if(p->m_nKey > pInsertNode->m_nKey){
            break;
        }//if
        pre = p;
        p = p->m_pNext;
    }//while

    // 插入
    pInsertNode->m_pNext = p;
    pre->m_pNext = pInsertNode;

    return dummy->m_pNext;
}