JavaScriptでチェーン操作-11 Alternating Splitを実現します.


TL;DR
一つのチェーンを交互に二つに切って、シリーズの目次を前書きと目次に見ます.
需要
一つの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の変数を使っています.サイクル毎に01とに交互に設定します.持続的に増加するidxを使用して、残りを取りに協力する人もいます.例えばidx % 2.やり方にはいろいろな種類があるので,詳しく述べる必要はない.
ここではdummy nodeのテクニックを使って、「最初のノードが空かどうかを判断する」ことを簡略化しています.この技術についてはインセンスノードを見てもいいです.
参考資料
Codewars Kata GitHubのコードはGitHubのテストを実現します.