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;
    }
  }
};

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

赞 (0)

相关推荐

  • 关于双向链表的增删改查和排序的C++实现

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;

  • C++实现单链表按k值重新排序的方法

    本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s

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

    本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN

  • python实现合并两个排序的链表

    剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码.写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码.上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!! 解题思路

  • java编程题之合并两个排序的链表

    本文实例为大家分享了java合并两个排序的链表,供大家参考,具体内容如下 /** * * 剑指offer编程题(JAVA实现)--第16题:合并两个排序的链表 * * 输入两个单调递增的链表,输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则. * */ public class Test16 { public static ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { // 首先判断

  • C++解决合并两个排序的链表问题

    C++解决合并两个排序的链表问题

    目录 题目描述: 示例: 解题思路: 测试代码: 题目描述: 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的. 数据范围: n为0~1000,节点值为-1000~1000 要求:空间复杂度 O(1),时间复杂度 O(n) 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示: 或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所

  • TypeScript合并两个排序链表的方法详解

    TypeScript合并两个排序链表的方法详解

    目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • JS实现的合并两个有序链表算法示例

    JS实现的合并两个有序链表算法示例

    本文实例讲述了JS实现的合并两个有序链表算法.分享给大家供大家参考,具体如下: 将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 可以直接运行的方案: <script> function Node(element) { this.element = element;//当前节点的元素 this.next = n

  • 逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表,即从一个链表的尾指针指向另一个链表的尾指针,依次逆转交替进行合并.下面就通过实例来详细的介绍该逆转交替合并两个链表的思路与实现代码. 一.问题描述 链表A和B A: 1->2->3->4 B: a->b->c->d 请逆转交替合并两个链表,示例结果如下: 4->d->3->c->2->b->1->a 节点类型定义如下: classNode { public Node next; ... } 二.源代码: 传

  • c语言合并两个已排序数组的示例(c语言数组排序)

    问题:将两个已排序数组合并成一个排序数组 这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法?),只做简单数组的处理. 简单代码如下: 说明:之所以把merge函数定义成返回数组长度,是因为后续会有重复数据合并功能的merge版本,考虑到接口一致性. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <string.h> int merge(int* ar1, int len1, int

随机推荐