【刷算法】合并两个排序的单链表

2501207950 发布于2019-08-22 18:26 / 2853人阅读

摘要：题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题目描述

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

分析

首先考虑两个链表的头部哪个成为新链表的头，显然是值小的那个是新的头；

然后是合并时，两个链表上分别有一个指针cur1和cur2，比较两个指针指向的节点值大小，较小的链接到新链表的尾部，且指针往后移动一个，较大的则不动；
可能有某个链表未遍历完，直接将其全添加到新链表尾部即可。

代码实现

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(h1, h2)
{
    if(h1 === null && h2 === null)
        return;
    if(h1 ===  null)
        return h2;
    if(h2 === null)
        return h1;
    
    var newH = null, cur1 = null, cur2 = null, newE = null;
    if(h1.val < h2.val){
        newH = h1;
        cur1 = h1.next;
        cur2 = h2;
    }
    else{
        newH = h2;
        cur1 = h1;
        cur2 = h2.next;
    }
    newE = newH;
    while (cur1 !== null && cur2  !== null) {
        if(cur1.val < cur2.val){
            newE.next = cur1;
            cur1 = cur1.next;
        }else{
            newE.next = cur2;
            cur2 = cur2.next; 
        } 
         newE = newE.next;
    }
    while(cur1 !== null){
        newE.next = cur1;
        cur1 = cur1.next;
    }
    while(cur2 !== null){
        newE.next = cur2;
        cur2 = cur2.next;
    }
    
    return newH;
}

海外云主机 GPU服务器合并两个单链表最佳适应算法c语言单链表链表排序算法单链表的顺序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95864.html

第7期 Datawhale 组队学习计划

马上就要开始啦这次共组织15个组队学习涵盖了AI领域从理论知识到动手实践的内容按照下面给出的最完备学习路线分类难度系数分为低、中、高三档可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 评论0 收藏0
【刷算法】翻转单链表的递归和非递归方法

摘要：题目描述输入一个链表，反转链表后，输出新链表的表头。分析典型的面试题以及大学数据结构课程常见题，没啥好分析的了代码实现递归版非递归版题目描述输入一个链表，反转链表后，输出新链表的表头。分析典型的面试题以及大学数据结构课程常见题，没啥好分析的了... 代码实现递归版 function ListNode(x){ this.val = x; this.next = ...

ziwenxie 2019-08-22 18:25 评论0 收藏0
从一道前端面试题谈起

摘要：但是题目非要弄成链表的形式，说实在的，我真没有见过前端什么地方还需要用链表这种结构的除了面试的时候，所以说这种题目对于实际工作是没什么用处的，但是脑筋急转弯的智商题既然这样出了，我们就来看看怎么解决它吧。今天在知乎上看到一个回答《为什么前端工程师那么难招？》，作者提到说有很多前端工程师甚至连单链表翻转都写不出来。说实话，来面试的孩子们本来就紧张，你要冷不丁问一句单链表翻转怎么写，估计...

darkbaby123 2019-08-23 17:53 评论0 收藏0
LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0
数据结构与算法——单链表练习

摘要：概述前面的文章说到了一种很基础的数据结构链表数据结构与算法链表，今天就来看看关于单链表的几种常见的操作，技术笔试的时候很大概率能够遇到其中的一些。 1. 概述前面的文章说到了一种很基础的数据结构——链表：数据结构与算法——链表，今天就来看看关于单链表的几种常见的操作，技术笔试的时候很大概率能够遇到其中的一些。多练习一下，对我们理解链表有很大的帮助，也能够提升我们的编码能力。废话不多说...

fuchenxuan 2019-08-16 15:48 评论0 收藏0