第39题(2019-09-12)：反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序 about interview HOT 1 OPEN

// 定义链表节点
class Node {
  constructor(v, last) {
    this.next = null
    this.value = v
    if (last) {
      last.next = this
    }
  }
}

let head = makeList(10)
console.info(toString(head))
head = invert(head, 3)
console.info(toString(head))

// 原链表:  0,1,2,3,4,5,6,7,8,9
// 反转后:  2,1,0,5,4,3,8,7,6,9

// ---- 核心** -----
/**
 * 链表每m个节点反转
 * @param {*} head
 * @param {*} n
 */
function invert(head, n) {
  let pre = new Node(999, null)
  pre.next = head
  let start = head
  let end = head
  // 缓存头
  head = pre
  let count = 1
  while (start && end) {
    // 查找需要反转的链表 end 节点
    if (count < n) {
      count++
      end = end.next
    } else {
      count = 1
      // 缓存对 end 之后的链表的索引
      let next = end.next
      // 反转 start -> ** ->  end 这段链表
      revert(start, next)
      // 反转成功后, end 节点是新链表的头了, 而 start 是尾了
      pre.next = end
      // 反转的链表连上剩下的链表
      start.next = next
      // 初始化下一段要反转的链表段
      pre = start
      start = next
      end = next
    }
  }
  return head.next
}

/**
 * 给定一个链表头和结束标记进行反转
 * @param {*} start
 * @param {*} endTag
 */
function revert(start, endTag) {
  let temp
  let pre = null
  while (start !== endTag) {
    temp = start.next
    start.next = pre
    pre = start
    start = temp
  }
  return pre
}

// ----工具-----

// 构造一个链表
function makeList(length) {
  const head = new Node(-1, null)
  Array.from({length}, (_, i) => i).reduce((last, key) => new Node(key, last), head)
  return head.next
}

// 打印链表
function toString(head) {
  let temp = new Node(999, null)
  temp.next = head
  let show = []
  while ((temp = temp.next)) {
    show.push(temp.value)
  }
  return show.join(',')
}