JavaScriptでチェーン操作-11 Alternating Splitを実現します.
2745 ワード
TL;DR
一つのチェーンを交互に二つに切って、シリーズの目次を前書きと目次に見ます.
需要
一つの
再帰版
コードは以下の通りです
別の再帰バージョン
コードは以下の通りです
サイクルバージョン
コードは以下の通りです
ここではdummy nodeのテクニックを使って、「最初のノードが空かどうかを判断する」ことを簡略化しています.この技術についてはインセンスノードを見てもいいです.
参考資料
Codewars Kata GitHubのコードはGitHubのテストを実現します.
一つのチェーンを交互に二つに切って、シリーズの目次を前書きと目次に見ます.
需要
一つの
alternatingSplit()
関数を実現して、一つのチェーンを二つに切ります.サブチェーンのノードは親チェーンの中で交互に現れているはずです.元のチェーンがa -> b -> a -> b -> a -> null
である場合、2つのサブチェーンはそれぞれa -> a -> a -> null
およびb -> b -> null
である.var list = 1 -> 2 -> 3 -> 4 -> 5 -> null
alternatingSplit(list).first === 1 -> 3 -> 5 -> null
alternatingSplit(list).second === 2 -> 4 -> null
結果を簡略化するために、関数は一つのContectオブジェクトに戻り、二つのサブチェーンを保存します.function Context(first, second) {
this.first = first
this.second = second
}
もし元のチェーンがnull
であるか、または一つのノードしかないなら、異常を投げ出すべきです.再帰版
コードは以下の通りです
function alternatingSplit(head) {
if (!head || !head.next) throw new Error('invalid arguments')
return new Context(split(head), split(head.next))
}
function split(head) {
const list = new Node(head.data)
if (head.next && head.next.next) list.next = split(head.next.next)
return list
}
この解法の核心的な考えはsplit
にあり、この方法はチェーンテーブルを受信し、奇数位のノードからなるサブチェーンテーブルを返す.したがって、アルゴリズム全体の解法は、簡単にnew Context(split(head), split(head.next))
で表されることができる.別の再帰バージョン
コードは以下の通りです
function alternatingSplitV2(head) {
if (!head || !head.next) throw new Error('invalid arguments')
return new Context(...splitV2(head))
}
function splitV2(head) {
if (!head) return [null, null]
const first = new Node(head.data)
const [second, firstNext] = splitV2(head.next)
first.next = firstNext
return [first, second]
}
ここでのsplitV2
の役割は、アルゴリズム全体の意味と同じである.チェーンテーブルを受信し、クロス分割された2つのサブチェーンテーブルを返す.第一サブチェーンの頭はもちろんnew Node(head.data)
です.第二サブチェーンは?実はsplitV2(head.next)
の最初のサブチェーンです.この論理を理解すれば再帰過程が分かります.サイクルバージョン
コードは以下の通りです
function alternatingSplitV3(head) {
if (!head || !head.next) throw new Error('invalid arguments')
const first = new Node()
const second = new Node()
const tails = [first, second]
for (let node = head, idx = 0; node; node = node.next, idx = idx ? 0 : 1) {
tails[idx].next = new Node(node.data)
tails[idx] = tails[idx].next
}
return new Context(first.next, second.next)
}
この考え方は、まず2つの変数でサブチェーンを表し、その後チェーン全体を巡回して、それぞれのサブチェーンにノードを交互に挿入します.唯一の考慮が必要なのは、各循環体の中でノードがどのチェーンを挿入するべきかを判断することです.私はidx
の変数を使っています.サイクル毎に0
と1
とに交互に設定します.持続的に増加するidx
を使用して、残りを取りに協力する人もいます.例えばidx % 2
.やり方にはいろいろな種類があるので,詳しく述べる必要はない.ここではdummy nodeのテクニックを使って、「最初のノードが空かどうかを判断する」ことを簡略化しています.この技術についてはインセンスノードを見てもいいです.
参考資料
Codewars Kata GitHubのコードはGitHubのテストを実現します.