摘要：需求實現函數把鏈表居中切分成兩個子鏈表一個前半部分，另一個后半部分。提示一個簡單的做法是計算鏈表的長度，然后除以得出前半部分的長度，最后分割鏈表。最后用把數組轉回鏈表。參考資料的代碼實現的測試

把一個鏈表居中切分成兩個，系列目錄見 前言和目錄 。

實現函數 frontBackSplit() 把鏈表居中切分成兩個子鏈表 -- 一個前半部分，另一個后半部分。如果節點數為奇數，則多余的節點應該歸類到前半部分中。例子如下，注意 front 和 back 是作為空鏈表被函數修改的，所以這個函數不需要返回值。

var source = 1 -> 3 -> 7 -> 8 -> 11 -> 12 -> 14 -> null
var front = new Node()
var back = new Node()
frontBackSplit(source, front, back)
front === 1 -> 3 -> 7 -> 8 -> null
back === 11 -> 12 -> 14 -> null

如果函數的任何一個參數為 null 或者原鏈表長度小于 2 ，應該拋出異常。

提示：一個簡單的做法是計算鏈表的長度，然后除以 2 得出前半部分的長度，最后分割鏈表。另一個方法是利用雙指針。一個 “慢” 指針每次遍歷一個節點，同時一個 ”快“ 指針每次遍歷兩個節點。當快指針遍歷到末尾時，慢指針正好遍歷到鏈表的中段。

這個 kata 主要考驗的是指針操作，所以解法用不上遞歸。

代碼如下：

function frontBackSplit(source, front, back) {
  if (!front || !back || !source || !source.next) throw new Error("invalid arguments")

  const array = []
  for (let node = source; node; node = node.next) array.push(node.data)

  const splitIdx = Math.round(array.length / 2)
  const frontData = array.slice(0, splitIdx)
  const backData = array.slice(splitIdx)

  appendData(front, frontData)
  appendData(back, backData)
}

function appendData(list, array) {
  let node = list
  for (const data of array) {
    if (node.data !== null) {
      node.next = new Node(data)
      node = node.next
    } else {
      node.data = data
    }
  }
}

解法思路是把鏈表變成數組，這樣方便計算長度，也方便用 slice 方法分割數組。最后用 appendData 把數組轉回鏈表。因為涉及到多次遍歷，這并不是一個高效的方案，而且還需要一個數組處理臨時數據。

代碼如下：

function frontBackSplitV2(source, front, back) {
  if (!front || !back || !source || !source.next) throw new Error("invalid arguments")

  let len = 0
  for (let node = source; node; node = node.next) len++
  const backIdx = Math.round(len / 2)

  for (let node = source, idx = 0; node; node = node.next, idx++) {
    append(idx < backIdx ? front : back, node.data)
  }
}

// Note that it uses the "tail" property to track the tail of the list.
function append(list, data) {
  if (list.data === null) {
    list.data = data
    list.tail = list
  } else {
    list.tail.next = new Node(data)
    list.tail = list.tail.next
  }
}

這個解法通過遍歷鏈表來獲取總長度并算出中間節點的索引，算出長度后再遍歷一次鏈表，然后用 append 方法選擇性地把節點數據加入 front 或 back 兩個鏈表中去。這個解法不依賴中間數據（數組）。

append 方法有個值得注意的地方。一般情況下把數據插入鏈表的末尾的空間復雜度是 O(n) ，為了避免這種情況 append 方法為鏈表加了一個 tail 屬性并讓它指向尾節點，讓空間復雜度變成 O(1) 。

代碼如下：

function frontBackSplitV3(source, front, back) {
  if (!front || !back || !source || !source.next) throw new Error("invalid arguments")

  let slow = source
  let fast = source

  while (fast) {
    // use append to copy nodes to "front" list because we don"t want to mutate the source list.
    append(front, slow.data)
    slow = slow.next
    fast = fast.next && fast.next.next
  }

  // "back" list just need to copy one node and point to the rest.
  back.data = slow.data
  back.next = slow.next
}

思路在開篇已經有解釋，當快指針遍歷到鏈表末尾，慢指針正好走到鏈表中部。但如何修改 front 和 back 兩個鏈表還是有點技巧的。

對于 front 鏈表，慢指針每次遍歷的數據就是它需要的，所以每次遍歷時把慢指針的數據 append 到 front 鏈表中就行（第 9 行）。

對于 back 鏈表，它所需的數據就是慢指針停下的位置到末尾。我們不用復制整個鏈表數據到 back ，只用復制第一個節點的 data 和 next 即可。這種 復制頭結點，共用剩余節點 的技巧經常出現在一些 Immutable Data 的操作中，以省去不必要的復制。這個技巧其實也可以用到上一個解法里。

Codewars Kata
GitHub 的代碼實現
GitHub 的測試