アルゴリズム逆転への道、1日3分。
前の記事コレクション
コード倉庫
GitHub: github.com/...
Gitee: gitee.com/inwsy/LeetC...
問題: 2つの順序付き連結テーブルのマージ
問題ソース
2つの昇順連結テーブルを新しい昇順連結テーブルにマージして返します。新しいリンクテーブルは、与えられた2つのリンクテーブルのすべてのノードを連結することで形成されます。
例
入力：1>2->4, 1->3->4
出力：1>1->2->3->4->4
解決策：反復
まず第一に、チェーンテーブルのデータ構造を理解する必要があります。これが明確でない場合、この問題はまったくプレイできません。
私は、チェーンテーブルを定義するコードを最初に書きます：
public class ListNode {
public int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
"これ"”.val = val;
}
public ListNode (int val, ListNode next) {
"これ"”.val = val;
"これ"”.next = next;
}
}
コードはとてもシンプルで、整数値を保持するデータ・フィールドを定義し、チェーン・テーブル上の別のノードを形成する別のListNodeへのポインタを定義します。
次にソートですが、私はそれがソートの2つの配列であれば、ほとんどの人が書き出すことができるはずだと信じて、実際には、ソートの連鎖リストと配列のソートは、肯定的な思考に似ているソートの直接のサイクルは、単純です。
アイデア単純なコードも単純ですが、私は単純に反復ソートを書いたコードを見てください：
// 激しい反復
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode 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;
}
非常に単純ではありませんが、チェーンテーブルの2つのノードのサイズを判断し、ポイントへのポインタを変更し、ループ、2つのノードが終了するためのNULLになるまでループします。
ループが終了したときに、l1とl2の最大1つは非NULLになることに注意する必要があります。
解決策：再帰
良い習慣に付着し、答えを見るために質問を終えた後、アイデアの一般的な並べ替えは何も巧妙ではありませんが、書くために別の方法を見た、この書き込みは正直であるが、また少し書くために総会。
これは少し恥ずかしいですが、私はとても恥知らずですが、そう直接出て、再帰このように、通常は基本的な書かないように、突然、突然私が少し書いてみましょうか、かなり難しい。
//
public ListNode mergeTwoLists_1(ListNode l1, 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;
}
}
再帰コードは非常にきれいに見えるし、きれいさの代償は、可読性が低下しています。
しかし、再び、再帰は、それが一般的でなくても、すべてのコーダーが精通している必要があります。
追記：また自分の欠点を見つけてしまいましたが、こうして毎日1つずつ欠点を補っていくのは、やはりいいものですね。
