LeetCode :21.2つの順序付きチェーンテーブルを結合

目次

タイトル

例

解法プローブ

解法1:反復法

解題構想

コード実装

複雑度分析

解法2:再帰法

解題構想

コード実装

複雑度分析

タイトル
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例
入力:

1->2->4, 1->3->4

出力:

1->1->2->3->4->4

かいほうたんせき
解法1:反復法
問題を解く構想.
1.空チェーンテーブルについては、 l1が空であれば戻る l2 l2が空であれば戻る l1.2.比較 l1と l2の最初のノードの値を比較し、値の小さいノードを連結後の新しいチェーンテーブルの最初のノードとして保存し、値の小さいノードのチェーンテーブルを1桁後ろに移動します.3.チェーンテーブルが空になるまで、2つのチェーンテーブルの残りのノードで小さな値を選択し続け、新しいチェーンテーブルの後ろにリンクします.4.2つのチェーンテーブルの長さが異なると、1つのチェーンテーブルが空になり、別のチェーンテーブルの残りのノードを新しいチェーンテーブルの末尾に接続します.
コード実装
C++実装:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        }

        //   dummy            ，          -1
        ListNode* dummy = new ListNode(-1);                 
        ListNode* cur = dummy;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }

            cur = cur->next;
        }

        if (l1 == nullptr) {
            cur->next = l2;
        } else if (l2 == nullptr) {
            cur->next = l1;
        }

        return dummy->next;
    }
};

GO実装:

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //          nil，         
    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    }

    //           ，   Next          
    dummy := &ListNode{}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            // cur   l1        
            //     l1 = l1.Next cur = cur.Next
            cur, l1 = cur.Next, l1.Next
        } else {
            cur.Next = l2
            cur, l2 = cur.Next, l2.Next
        }
    }

    //      ，              ，           ，         
    if l1 == nil {
        cur.Next = l2
    } else if l2 == nil {
        cur.Next = l1
    }

    return dummy.Next
}

複雑度分析
時間複雑度(O(n+m))(nがチェーンテーブル1の長さ、mがチェーンテーブル2の長さと仮定)空間複雑度(O(1))
解法2:再帰法
問題を解く構想.
1.空チェーンテーブルについては、 l1が空であれば戻る l2 l2が空であれば戻る l1.2.2つのチェーンテーブルの最初のノードのサイズを比較し、ヘッダノードの位置を決定します.3.ヘッダノードが確定した後、2つのチェーンテーブルの残りのノードの中から小さいノードを選択して第2ステップで選択したノードの後ろにリンクし続け、チェーンテーブルが空になるまで第2、3ステップを繰り返します.
コード実装
C++実装:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        }

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

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

            return l2;
        }
    }
};

GO実装:

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //          nil，         
    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    }

    //  ListNode       new       ，      dummy := new(ListNode)      
    dummy := &ListNode{}

    //           
    newHead := dummy

    if l1.Val < l2.Val {
        newHead = l1
        newHead.Next = mergeTwoLists(l1.Next, l2)
    } else {
        newHead = l2
        newHead.Next = mergeTwoLists(l2.Next, l1)
    }

    return newHead
}

複雑度分析
時間複雑度(O(n+m))(nがチェーンテーブル1の長さ、mがチェーンテーブル2の長さと仮定)空間複雑度(O(n+m))
個人用ページ:
www.codeapes.cn