亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++解決合并兩個(gè)排序的鏈表問(wèn)題

 更新時(shí)間：2021年12月07日 14:18:52   作者：翟天保Steven  
本文主要介紹了通過(guò)C++解決合并兩個(gè)排序的鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。文中代碼講解詳細(xì)，有需要的朋友可以參考一下

題目描述：

輸入兩個(gè)遞增的鏈表，單個(gè)鏈表的長(zhǎng)度為n，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

數(shù)據(jù)范圍： n為0~1000，節(jié)點(diǎn)值為-1000~1000

要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

如輸入{1,3,5},{2,4,6}時(shí)，合并后的鏈表為{1,2,3,4,5,6}，所以對(duì)應(yīng)的輸出為{1,2,3,4,5,6}，轉(zhuǎn)換過(guò)程如下圖所示：

或輸入{-1,2,4},{1,3,4}時(shí)，合并后的鏈表為{-1,1,2,3,4,4}，所以對(duì)應(yīng)的輸出為{-1,1,2,3,4,4}，轉(zhuǎn)換過(guò)程如下圖所示：

示例：

輸入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

解題思路：

本題考察數(shù)據(jù)結(jié)構(gòu)鏈表的使用。有兩種解法：

  1. 遍歷比較。建立一個(gè)新的頭節(jié)點(diǎn)head后，用cur指針指向下一節(jié)點(diǎn)；然后依次比較兩個(gè)子鏈表節(jié)點(diǎn)的值大小，誰(shuí)小先塞誰(shuí)，塞完就將其指向下一個(gè)節(jié)點(diǎn)；直到某個(gè)子鏈表遍歷完，將cur的next指向沒(méi)遍歷完的那個(gè)鏈表當(dāng)前的節(jié)點(diǎn)。
  2. 遞歸。從pHead1和pHead2的頭節(jié)點(diǎn)開(kāi)始比較，誰(shuí)小就返回誰(shuí)，然后其下一個(gè)指向，指向Merge函數(shù)的結(jié)果，Merge輸入的兩個(gè)鏈表為小的一方的next和大的一方的頭節(jié)點(diǎn)，也就是用下一個(gè)值和它繼續(xù)比誰(shuí)更??；依次類(lèi)推，遞歸中斷的標(biāo)志是有其中一個(gè)子鏈表指向nullptr，返回另一方即可。

測(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 *head=new ListNode(-1);
        ListNode *cur=head;
        while(pHead1&&pHead2)
        {
            if(pHead1->val<=pHead2->val)
            {
                cur->next=pHead1;
                pHead1=pHead1->next;
            }
            else{
                cur->next=pHead2;
                pHead2=pHead2->next;
            }
            cur=cur->next;
        }
        cur->next=pHead1?pHead1:pHead2;
        return head->next;
    }
};

解法二，遞歸：??

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1)
            return pHead2;
        if(!pHead2)
            return pHead1;
        if(pHead1->val<=pHead2->val)
        {
            pHead1->next=Merge(pHead1->next,pHead2);
            return pHead1;
        }
        else{
            pHead2->next=Merge(pHead1,pHead2->next);
            return pHead2;
        }
    }
};

到此這篇關(guān)于C++解決合并兩個(gè)排序的鏈表問(wèn)題的文章就介紹到這了,更多相關(guān)C++ 合并兩個(gè)排序的鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論