摘要：需求實(shí)現(xiàn)函數(shù)把鏈表居中切分成兩個(gè)子鏈表一個(gè)前半部分，另一個(gè)后半部分。提示一個(gè)簡(jiǎn)單的做法是計(jì)算鏈表的長(zhǎng)度，然后除以得出前半部分的長(zhǎng)度，最后分割鏈表。最后用把數(shù)組轉(zhuǎn)回鏈表。參考資料的代碼實(shí)現(xiàn)的測(cè)試

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

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

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

如果函數(shù)的任何一個(gè)參數(shù)為 null 或者原鏈表長(zhǎng)度小于 2 ，應(yīng)該拋出異常。

提示：一個(gè)簡(jiǎn)單的做法是計(jì)算鏈表的長(zhǎng)度，然后除以 2 得出前半部分的長(zhǎng)度，最后分割鏈表。另一個(gè)方法是利用雙指針。一個(gè) “慢” 指針每次遍歷一個(gè)節(jié)點(diǎn)，同時(shí)一個(gè) ”快“ 指針每次遍歷兩個(gè)節(jié)點(diǎn)。當(dāng)快指針遍歷到末尾時(shí)，慢指針正好遍歷到鏈表的中段。

這個(gè) kata 主要考驗(yàn)的是指針操作，所以解法用不上遞歸。

代碼如下：

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
    }
  }
}

解法思路是把鏈表變成數(shù)組，這樣方便計(jì)算長(zhǎng)度，也方便用 slice 方法分割數(shù)組。最后用 appendData 把數(shù)組轉(zhuǎn)回鏈表。因?yàn)樯婕暗蕉啻伪闅v，這并不是一個(gè)高效的方案，而且還需要一個(gè)數(shù)組處理臨時(shí)數(shù)據(jù)。

代碼如下：

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
  }
}

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

append 方法有個(gè)值得注意的地方。一般情況下把數(shù)據(jù)插入鏈表的末尾的空間復(fù)雜度是 O(n) ，為了避免這種情況 append 方法為鏈表加了一個(gè) tail 屬性并讓它指向尾節(jié)點(diǎn)，讓空間復(fù)雜度變成 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
}

思路在開篇已經(jīng)有解釋，當(dāng)快指針遍歷到鏈表末尾，慢指針正好走到鏈表中部。但如何修改 front 和 back 兩個(gè)鏈表還是有點(diǎn)技巧的。

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

對(duì)于 back 鏈表，它所需的數(shù)據(jù)就是慢指針停下的位置到末尾。我們不用復(fù)制整個(gè)鏈表數(shù)據(jù)到 back ，只用復(fù)制第一個(gè)節(jié)點(diǎn)的 data 和 next 即可。這種 復(fù)制頭結(jié)點(diǎn)，共用剩余節(jié)點(diǎn) 的技巧經(jīng)常出現(xiàn)在一些 Immutable Data 的操作中，以省去不必要的復(fù)制。這個(gè)技巧其實(shí)也可以用到上一個(gè)解法里。

Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試