Merge Two Sorted Lists -- LeetCode

原題リンク:  http://oj.leetcode.com/problems/merge-two-sorted-lists/
 
このテーマは比較的簡単で、古典的なチェーンテーブルの基本的な操作です.2つのポインタが2つのチェーンテーブルに対応することを維持します.通常、1つのチェーンテーブルを基準にします.例えば、l 1です.l 1の当期の要素が小さい場合は、l 1を直接移動します.そうしないと、l 2の現在の要素をl 1の現在の要素の前に挿入します.アルゴリズム時間複雑度はO(m+n)であり,mとnはそれぞれ2つのチェーンテーブルの長さであり,空間複雑度はO(1)であり,コードは以下の通りである.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode helper = new ListNode(0);
    ListNode pre = helper;
    helper.next = l1;
    while(l1!=null && l2 != null)
    {
        if(l1.val>l2.val)
        {
            ListNode next = l2.next;
            l2.next = pre.next;
            pre.next = l2;
            l2 = next;
        }
        else
        {
            l1 = l1.next;
        }
        pre = pre.next;

    }
    if(l2!=null)
    {
        pre.next = l2;
    }
    return helper.next;
}

この問題に似ているのはMerge Sorted Arrayです
あ、ただ後者は配列をマージする操作で、面接で一緒に聞くかもしれません.拡張テーマMerge k Sorted Lists
ああ、これは分散システムで役立つ基本的な操作なのか、それとも重視する必要があるのか、面接では多くの問題を発散することができます.