【LeetCode】21. 合併兩個有序連結串列

語言: CN / TW / HK

date created: '2022-08-01 00:52' date updated: '2022-08-01 01:58' theme: devui-blue highlight: a11y-dark


攜手創作,共同成長!這是我參與「掘金日新計劃 · 8 月更文挑戰」的第1天,點選檢視活動詳情

前言

為了養成創作習慣,從今天起開始刷力扣了,只刷簡單和中等難度的題,分類刷,這個月就先刷連結串列題,從簡單的開始按著順序刷,一天一道,養生做法。

為了鍛鍊一下自己,決定用 C 來寫,據說是受苦,不過一天一道無所謂了。

image.png

題目描述

21. 合併兩個有序連結串列 - 力扣(LeetCode)

將兩個升序連結串列合併為一個新的 升序 連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。 

示例 & 提示

示例 1:

輸入:l1 = [1,2,4], l2 = [1,3,4] 輸出:[1,1,2,3,4,4]

示例 2:

輸入:l1 = [], l2 = [] 輸出:[]

示例 3:

輸入:l1 = [], l2 = [0] 輸出:[0]

提示:

  • 兩個連結串列的節點數目範圍是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非遞減順序 排列

思路

  • 先想暴力做法,新建一個連結串列,同時掃描兩個連結串列,比較結點值大小,小的直接插入新連結串列,大的繼續比較,以此類推...

  • 由於連結串列沒有頭結點,還得先比較兩個連結串列的第一個元素的大小,找到最小的元素作為新連結串列的頭

  • 最後可能會有一個連結串列有剩餘結點,直接全部插入新連結串列
  • 最簡單的還得是遞迴,但是對於不熟悉遞迴的人實在是比較難想到🦥

具體程式碼

兩種方法全都是 beats 100%,用 C 的好處嗎?

```c struct ListNode mergeTwoLists(struct ListNode l1, struct ListNode *l2) { if (l1 == NULL) { return l2; }

if (l2 == NULL) {
    return l1;
}

struct ListNode *head, *p;
if (l1->val <= l2->val) {
    head = l1;
    l1 = l1->next;
} else {
    head = l2;
    l2 = l2->next;
}

p = head;
while (l1 != NULL && l2 != NULL) {
    if (l1->val <= l2->val) {
        p->next = l1;
        l1 = l1->next;
    } else {
        p->next = l2;
        l2 = l2->next;
    }
    p = p->next;
}

if (l1 != NULL) {
    p->next = l1;
} else {
    p->next = l2;
}
return head;

} ```

```c struct ListNode mergeTwoLists(struct ListNode l1, struct ListNode *l2) { if (l1 == NULL) { return l2; }

if (l2 == NULL) {
    return l1;
}

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

} ```