資料結構學習-LeetCode21.合并兩個有序鏈表C語言

LeetCode21.合并兩個有序鏈表
難度 簡單
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

資料結構是編程的基礎，它決定了一個程式員的發展潛力，所以練好資料結構還是很重要的，
最近我會先在力扣上將資料結構的題寫一遍（先用C語言寫），并將總結與感想記錄在我的博客里，
（Ps：蒟蒻一枚，求大佬輕點噴）

對于這道題目，最開始我的做法是暴力破解，大概思路如下：

先分別找到list1與list2鏈表中的最小節點，然后比較將更小的那個節點添加到新的鏈表中去，用while回圈這一程序直至有一個鏈表為NULL結束回圈，
然后將兩個鏈表中不為NULL的鏈表添加到新鏈表中去，最后回傳新鏈表，

看完官方題解后發現這個方法屬實笨(～￣(OO)￣)ブ，又耗時間，又占記憶體，需要開好幾個指標，
不過由于測驗資料不穩定的原因，最終的測驗結果一點波動，最好的情況耗時0ms，打敗100%用戶（我當時一臉懵逼，不應該呀，這個演算法），最壞8ms，打敗8%用戶......
可能也許maybe時間復雜度為O(n³)?空間復雜度我也不會算，開了這么多指標估計也不會低，至少是O(n+m)吧....

代碼如下：
我先定義了這么多指標，，，看著就令人頭皮發麻

    struct ListNode* newList;   //新鏈表
    struct ListNode* headL1;    //list1鏈表指標
    struct ListNode* headL2;    //list2鏈表指標
    struct ListNode* headNew;   //新鏈表指標
    struct ListNode* newNode;   //添加的新節點
    struct ListNode* ptrA;  //查找list1中最小值的指標
    struct ListNode* ptrB;  //查找list2中最小值的指標

然后進行初始化設定：

    newList = (ListNode*)malloc(sizeof(ListNode));
    headL1 = l1->next;
    headL2 = l2->next;
    headNew = newList;

接著就開始在while回圈里面依次查找最小值，然后比較，把更小的值添加到新鏈表中去：

while (headL1 != NULL && headL2 != NULL){
    //1.分別找到兩個鏈表中的最小值 
    int minA = headL1->val;
    int minB = headL2->val;
    ptrA = headL1;
    ptrB = headL2;
    //回圈鏈表1，找到最小值
    while (ptrA != NULL){
	if (minA > ptrA->val) minA = ptrA->val;
        ptrA = ptrA->next;
    }
    //回圈鏈表2，找到最小值
    while (ptrB != NULL){
        if (minB > ptrB->val) minB = ptrB->val;
	ptrB = ptrB->next;	
    }
    //2.找出兩個最小值中的最小值，并將其賦給新的結點 
    newNode = (ListNode*)malloc(sizeof(ListNode));
    if (minA < minB){
        newNode->val = minA;
        //如果最小值在list1中，就將list1的指標往后移
        headL1 = headL1->next;
    }else{
	newNode->val = minB;
        //如果最小值在list2中，就將list2的指標往后移
	headL2 = headL2->next;
    }
    //將節點賦給新鏈表 
    headNew->next = newNode;
    //讓新鏈表的指標往后移
    headNew = newNode;
}

好吧，我知道很蠢，求噴輕點QAQ
接下來就是把兩個鏈表中比較長的那一個鏈表未遍歷完的節點（已排好序的）添加到新鏈表上去
這是我自己想出來的做法：

	//如果第一個鏈表為空了，將第二個鏈表剩余的添加到新鏈表 
	if (headL1 == NULL && headL2 != NULL){
		ptrB = headL2;
		while (ptrB != NULL){
			newNode = (ListNode*)malloc(sizeof(ListNode));
			newNode->val = ptrB->val;
			headNew->next = newNode;
			headNew = newNode;
			ptrB = ptrB->next;
		}
	}
	//如果第二個鏈表為空了，將第一個鏈表剩余的添加到新鏈表 
	if (headL1 != NULL && headL2 == NULL){
		ptrA = headL1;
		while (ptrA != NULL){
			newNode = (ListNode*)malloc(sizeof(ListNode));
			newNode->val = ptrA->val;
			headNew->next = newNode;
			headNew = newNode;
			ptrA = ptrA->next;
		}
	}

這是我看了官方題解后發做法：

    headNew->next = headL1 == NULL ? headL2 : headL1;

接著回傳newList->next就可以了，，，
讓我們快點跳過這個羞恥的做法，去看看官解吧QAQ

解法一：遞回 時間復雜度為O(n+m) 空間復雜度為O(n+m)

這個已經可以把我的解法按在地上摩擦了...
先上代碼再講解：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if (l1 == NULL){
        return l2;
    }else if (l2 == NULL){
	return l1;
    }else if (l1->val < l2->val){
	l1->next = mergeTwoLists(l1->next, l2);
	return l1;
    }else{
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

首先，要用遞回就得有出口，不給函式提供出口的話就會一直死回圈的執行下去

我們的出口就是當兩個鏈表其中一個遍歷完后（即指標指向為NULL）就退出回圈，并將另一個鏈表回傳（也就是把剩下的數接到最后一個指標上面去）
在這個解法上我們不用新開鏈表，只需要假象存在一個新的鏈表，然后list1與list2分別為兩個鏈表的指標，
讓指標指向的元素比較大小，較小的元素指標后移，下一次遞回里我們再比較當前兩個指標指向元素的大小

如圖有兩個鏈表listA與liistB，遞回時我們先比較A1與B1大小，1 < 2，
所以listA指標后移，listB指標不變
文字太抽象，直接上圖

（gif圖片大小咋調整喲QAQ）
最終遞回結束后將節點從6依次回傳

解法二：迭代

代碼先走起

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* preHead;
    preHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* prev;
    prev = preHead;
    while(l1 != NULL && l2 != NULL){
	if (l1->val <= l2->val){
	    prev->next = l1;
   	    l1 = l1->next;
	}else{
	    prev->next = l2;
	    l2 = l2->next;
	}
	prev = prev->next;
    }
    prev->next = l1 == NULL ? l2 : l1; 
    return preHead->next;
}

這里我們需要創建兩個指標變數，一個為頭指標preHead方便之后回傳最終鏈表，另一個為prev用來指向當前元素的（即定位功能，類似于方向標）（注意，這里了l1和l2也是指向元素的作用）
同樣的，回圈的終止條件為兩個鏈表中有其中一個被遍歷完就終止回圈
在回圈中比較l1和l2指向的元素大小，讓prev指標指向其中較小元素的節點，依此回圈下去，回圈結束后依然把剩余的節點接到prev后面，
法二可以直接去看力扣官方題解的動圖，講的很詳細，
按我的理解，這里的preHead就像一個無家可歸的孩子，而prev就是給他指向回家路的好心人，他要判別哪條路才能讓preHead回到家，這樣他就不得不比較每個元素的大小，選取較小的元素作為下一條正確的回家路，最終prev將所有路連起來，然后我們回傳第一條路（即preHead->next)，讓這位孩紙按著鏈表的路走回家，

如果有不好的地方歡迎大家在評論區討論呀

（當然這題比較簡單，以后我會持續更新學習資料結構的記錄的）

標籤：其他

上一篇：0098. Validate Binary Search Tree (M)

下一篇：字符流中第一個不重復的字符