C++实现合并两个排序的链表

 更新时间:2019年03月03日 14:40:21   作者:francis_xd   我要评论

这篇文章主要为大家详细介绍了C++实现合并两个排序的链表,具有一定的参考价值,感兴趣的小伙伴们可以参?#23478;?#19979;

本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下

问题描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

struct ListNode {
  int val;
  struct ListNode *next;
  ListNode(int x) :
  val(x), next(NULL) {
  }
};

方法一

class Solution {
public:
  ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  {
    ListNode* newList = NULL; //新链表头
    ListNode* newListRear = NULL; //新链表尾
    // 先处理某个链表为空的情形
    if (pHead1 == NULL){
      return pHead2;
    }
    if (pHead2 == NULL){
      return pHead1;
    }
    // 把数值小的结点放入新链表,生成?#26041;?#28857;
    if (pHead1->val <= pHead2->val){
      newList = pHead1;
      newListRear = pHead1;
      pHead1 = pHead1->next;
    }else{
      newList = pHead2 ;
      newListRear = pHead2;
      pHead2 = pHead2->next;
    }
    // 两表均不空的情形下,遍历 
    while (pHead1 != NULL && pHead2 != NULL) {
      if (pHead1->val <= pHead2->val) {
        newListRear->next =pHead1;
        newListRear = pHead1;
        pHead1 = pHead1->next;
      }else{
        newListRear->next =pHead2;
        newListRear = pHead2;
        pHead2 = pHead2->next;
      }
    }
    //某一表为空时,把另一表接入新表表尾 
    if (pHead1 == NULL) {
      newListRear->next = pHead2;
    }
    if (pHead2 == NULL) {
      newListRear->next = pHead1;
    }
    
    return newList;
  }
};

方法二(递归思想)

class Solution {
public:
  ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  {
    if (pHead1 == NULL){
      return pHead2;
    }
    if (pHead2 == NULL){
      return pHead1;
    }
    
    if (pHead1->val <= pHead2->val){ // pHead1为合并后的?#26041;?#28857;
      pHead1->next = Merge(pHead1->next, pHead2);
      return pHead1;
    }else{ // pHead2 为合并后的?#26041;?#28857;
      pHead2->next = Merge(pHead1, pHead2->next);
      return pHead2;
    }
  }
};

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

相关文章

最新评论

辽宁35选7开奖结果
郑州11选5 彩票走势图首页 彩票北京十一选五 中国福彩开奖查询 新浪nba 刘伯温四肖中特料 pk10怎么看走势图选号 11选五开奖走势图 贵州11选5五码走势图 360福彩开奖结果查询 澳洲三分彩计划软件 江苏11选5对几个才中奖 四川体育彩票走势图 浙江11选5定牛走势图 极速11选5怎么