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

本文实例为大家分享了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;    }    // 把数值小的结点放入新链表,生成头节点    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为合并后的头节点     pHead1->next = Merge(pHead1->next, pHead2);     return pHead1;    }else{ // pHead2 为合并后的头节点     pHead2->next = Merge(pHead1, pHead2->next);     return pHead2;    }   }  };  

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。

—-想了解C++实现合并两个排序的链表分享!全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

www.ctvol.com true Article C++实现合并两个排序的链表分享!

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/482886.html

(0)
上一篇 2020年11月9日 下午6:32
下一篇 2020年11月9日 下午6:36

精彩推荐