合併兩個排序的列表Leetcode解決方案  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 第一資本 Facebook 谷歌 IBM Microsoft微軟 神諭
算法 編碼 訪問 面試準備 力碼 力碼解決方案 鍊錶

鍊錶 在線性特性上很像數組。 我們可以合併兩個排序的數組以形成一個整體的排序數組。 在這個問題上,我們必須合併兩個排序的鍊錶 到位 以排序方式返回包含兩個列表元素的新列表。

例  

合併兩個排序的列表Leetcode解決方案

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

途徑  

最簡單的方法是使用 兩分球 技術。 創建一個新的空列表。 在兩個指針之間附加較小的元素,並遞增相應的指針。 這是一個很好的方法,但是需要創建一個額外的列表,該列表會佔用空間。

最佳方法僅應消耗恆定的空間才能執行 到位 排序。 我們可以遵循迭代方法。 我們已經將節點存儲在兩個列表中。 創建一個新的列表指針及其後續的“下一個指針”應指向內存中的預定義節點。 在此過程中,我們創建了 沒有 新節點。

算法(幼稚方法)  

  1. 創建一個功能 mergeTwoSortedLists() 需要兩個列表指針作為參數
  2. 如果其中一個列表是 空值, 退還另一個
  3. 創建一個 溫度 指向兩個列表頭中較小節點的變量
  4. 現在,至少要在我們的結果上附加一個節點,所以應該增加一個頭
  5. 這將產生一個子問題。 因此,調用相同的遞歸函數並將其附加到temp
  6. 如果List1.value <List2.value
    • 溫度= 新的ListNode(List1.value) ,temp-> next = mergeTwoSortedLists(List1-> next,List2)
  7. 如果List2.value <= List1.value
    • 溫度= 新的ListNode(List2.value) ,temp-> next = mergeTwoSortedLists(List1,List2-> next)
  8. 退貨說明 溫度 得到想要的清單
也可以看看
插入間隔Leetcode解決方案

算法(最佳)  

  1. 創建一個新的列表指針,將其稱為 dummy_head。
  2. 保持其“”(複製指針),以便我們可以訪問列表 地址。
  3. 在“下一個指針應該以某種方式操縱dummy_head,使其指向列表中的預定義節點 l1l2.
  4. 我們可以通過以下方式完成上述任務:
    • 始終使用從頭開始的指針對列表進行迭代。
    • 除非完全遍歷列表之一:
      • 將兩個列表指針中值較小的節點追加到 dummy_head, 遞增相應的指針。
    • 現在,至少有一個指針是 空值。 因此,附加 非空 列出到虛擬頭。
  5. 返回 虛擬列表的。

履行  

合併兩個排序列表的C ++程序

天真的方法

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

最佳方法

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

合併兩個排序列表的Java程序

天真的方法

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

最佳方法

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

複雜度分析  

時間複雜度 合併兩個排序列表

O(N + M), 哪裡 NM 是兩個列表的長度。 我們在兩種方法中都遍歷了兩個列表,因此這兩種算法都是線性的。

也可以看看
有效的Perfect Square Leetcode解決方案

空間複雜度 合併兩個排序列表

在最佳方法中,重要的是要了解我們只 操縱指針。 因此,變量的恆定空間說明了內存的使用情況。 因此,最佳方法的空間複雜度為 O(1). O(N + M) 在討論的幼稚方法中使用了空格。