#include "OJ.h"

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

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

返回: 正常插入节点返回链表头指针，其它异常返回空指针
*/
ListNode* InsertNodeToList(ListNode* pListHead, ListNode* pInsertNode)
{
	/*在这里实现功能*/
    
	if ((ListNode *)NULL == pListHead )
	{
        return (ListNode *)(NULL);
	}
    if ((ListNode *)NULL == pInsertNode )
    {
        return (ListNode *)(NULL);
    }
    if (pInsertNode->m_nKey < pListHead->m_nKey)
    {
        pInsertNode->m_pNext = pListHead;
        pListHead = pInsertNode;
        return (ListNode *)pListHead;
    }
	ListNode* p = pListHead;
    
    while ((ListNode *)NULL != p->m_pNext && p->m_pNext->m_nKey < pInsertNode->m_nKey)
    {
        p = p->m_pNext;
    }
   
    pInsertNode->m_pNext = p->m_pNext;
    p->m_pNext = pInsertNode;
	return (ListNode *)pListHead;
}

int main()
{
    ListNode astListNode[2];
    ListNode stInsertNode;
    ListNode *pListHead;

    astListNode[0].m_nKey = 2;
    astListNode[0].m_pNext = &astListNode[1];

    astListNode[1].m_nKey = 3;
    astListNode[1].m_pNext =(ListNode *)(NULL);

    stInsertNode.m_nKey = 4;
    stInsertNode.m_pNext =(ListNode *)(NULL);

    pListHead = InsertNodeToList(astListNode, &stInsertNode);
    return 0;
}

向升序单向链表中插入一个节点