DFSの簡単な説明
深さ優先探索（DFS：Depth-First Search）は、木やグラフなどのデータ構造を探索するためのアルゴリズムの一つです。DFSは、可能な限り深くノードを探索してから次の分岐に進むという方法で動作します。再帰やスタックを使って実装することが多いです。
問題の解法の説明
以下は、与えられたシングルリンクリストを0を基準に値をマージする問題の解法をDFSを用いて説明したものです。
/**
* シングルリンクリストのノードを定義するクラス。
*/
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode mergeNodes(ListNode head) {
// 新しいリストの先頭ノードを生成
ListNode current = new ListNode();
// 再帰的にDFSを使ってノードをマージ
dfs(head, current);
// マージされたリストの先頭ノードを返す
return current;
}
ListNode dfs(ListNode param, ListNode current) {
// 基底条件：リストの終端に達した場合
if (param.next == null) {
return current;
}
// ノードの値が0の場合
if (param.val == 0) {
// currentノードが0でない場合、新しいノードを作成して次へ進む
if (current.val != 0) {
current.next = new ListNode();
return dfs(param, current.next);
} else {
// currentノードの値が0の場合、値を0に設定
current.val = 0;
}
}
// currentノードに現在のノードの値を加算
current.val += param.val;
// 次のノードへ進む
param = param.next;
// 再帰呼び出し
return dfs(param, current);
}
}
コードの説明
-
ListNode クラスの定義
- シングルリンクリストのノードを定義します。各ノードは val という値と next という次のノードへの参照を持っています。
-
Solution クラスと mergeNodes メソッド
- mergeNodes メソッドは、リストの先頭ノード head を入力として受け取り、マージされた新しいリストを返します。
- 新しいリストの先頭ノード current を生成し、再帰関数 dfs を使ってノードをマージします。
-
dfs メソッド
- dfs メソッドは再帰的にリストを探索し、0を基準に値をマージします。
- 基底条件：現在のノード param の次のノードが null ならば、現在のノード current を返します。
- 現在のノードの値が0の場合：
- current ノードの値が0でない場合、新しい ListNode を生成し、再帰呼び出しを行います。
- current ノードの値が0の場合、値を0に設定します。
- 現在のノードの値が0でない場合：
- 現在のノードの値を current ノードの値に加算します。
- param ノードを次のノードに進めます。
- dfs メソッドを再帰的に呼び出して次のノードに進みます。
このようにして、DFSを用いてシングルリンクリストの値をマージし、新しいリストを生成することができます。
Summary
この問題は、Call By Reference方式でオブジェクトが伝達されることを利用する問題でした。 DFSはStack Memoryに影響を受けるので注意してください。