【刷算法】合并兩個(gè)排序的單鏈表

2501207950 發(fā)布于2019-08-22 18:26 / 2969人閱讀

摘要：題目描述輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

題目描述

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

分析

首先考慮兩個(gè)鏈表的頭部哪個(gè)成為新鏈表的頭，顯然是值小的那個(gè)是新的頭；

然后是合并時(shí)，兩個(gè)鏈表上分別有一個(gè)指針cur1和cur2，比較兩個(gè)指針指向的節(jié)點(diǎn)值大小，較小的鏈接到新鏈表的尾部，且指針往后移動(dòng)一個(gè)，較大的則不動(dòng)；
可能有某個(gè)鏈表未遍歷完，直接將其全添加到新鏈表尾部即可。

代碼實(shí)現(xiàn)

/*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云服務(wù)器云服務(wù)器合并兩個(gè)單鏈表最佳適應(yīng)算法c語言單鏈表鏈表排序算法單鏈表的順序

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/95864.html

相關(guān)文章

第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

馬上就要開始啦這次共組織15個(gè)組隊(duì)學(xué)習(xí) 涵蓋了AI領(lǐng)域從理論知識(shí)到動(dòng)手實(shí)踐的內(nèi)容按照下面給出的最完備學(xué)習(xí)路線分類難度系數(shù)分為低、中、高三檔可以按照需要參加 - 學(xué)習(xí)路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 評(píng)論0 收藏0
【刷算法】翻轉(zhuǎn)單鏈表的遞歸和非遞歸方法

摘要：題目描述輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。分析典型的面試題以及大學(xué)數(shù)據(jù)結(jié)構(gòu)課程常見題，沒啥好分析的了代碼實(shí)現(xiàn)遞歸版非遞歸版題目描述輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。分析典型的面試題以及大學(xué)數(shù)據(jù)結(jié)構(gòu)課程常見題，沒啥好分析的了... 代碼實(shí)現(xiàn) 遞歸版 function ListNode(x){ this.val = x; this.next = ...

ziwenxie 2019-08-22 18:25 評(píng)論0 收藏0
從一道前端面試題談起

摘要：但是題目非要弄成鏈表的形式，說實(shí)在的，我真沒有見過前端什么地方還需要用鏈表這種結(jié)構(gòu)的除了面試的時(shí)候，所以說這種題目對(duì)于實(shí)際工作是沒什么用處的，但是腦筋急轉(zhuǎn)彎的智商題既然這樣出了，我們就來看看怎么解決它吧。今天在知乎上看到一個(gè)回答《為什么前端工程師那么難招？》，作者提到說有很多前端工程師甚至連單鏈表翻轉(zhuǎn)都寫不出來。說實(shí)話，來面試的孩子們本來就緊張，你要冷不丁問一句單鏈表翻轉(zhuǎn)怎么寫，估計(jì)...

darkbaby123 2019-08-23 17:53 評(píng)論0 收藏0
LeetCode 之 JavaScript 解答第23題 —— 合并K個(gè)有序鏈表（Merge K S

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(guān)聯(lián)原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿題目：Merge K...

zhou_you 2019-08-23 16:53 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法——單鏈表練習(xí)

摘要：概述前面的文章說到了一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)鏈表數(shù)據(jù)結(jié)構(gòu)與算法鏈表，今天就來看看關(guān)于單鏈表的幾種常見的操作，技術(shù)筆試的時(shí)候很大概率能夠遇到其中的一些。 1. 概述前面的文章說到了一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)——鏈表：數(shù)據(jù)結(jié)構(gòu)與算法——鏈表，今天就來看看關(guān)于單鏈表的幾種常見的操作，技術(shù)筆試的時(shí)候很大概率能夠遇到其中的一些。多練習(xí)一下，對(duì)我們理解鏈表有很大的幫助，也能夠提升我們的編碼能力。廢話不多說...

fuchenxuan 2019-08-16 15:48 評(píng)論0 收藏0