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¿ª½±½á¹û