[华为机试练习题]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;
}
目录
相关文章
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
14天前
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
14天前
04_两两交换链表中的节点
04_两两交换链表中的节点
|
2月前
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。
LeetCode第23题合并 K 个升序链表
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
45 5
|
2月前
|
存储 算法 Python
【面试题】合井K个升序链表
【面试题】合井K个升序链表
31 0
|
2月前
|
存储 JavaScript 前端开发
JavaScript实现单向链表
JavaScript实现单向链表
17 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
34 2