0143. 重排链表.md

143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reorder-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 找中点
• 反转
• 合并

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if (!head || !head.next || !head.next.next) return head
  
  var h = head, t = head
  while (t.next) {
    h = h.next
    t = t.next
    if (t.next) {
      t = t.next
    }
  }

  var r = h.next, prev = h
  h.next = null
  while (r) {
    var next = r.next
    r.next = prev
    prev = r
    r = next
  }


  h = head 
  while (true) {
    var next = h.next
    var tnext = t.next
    h.next = t
    t.next = next
    h = next
    t = tnext
    if (h === t || h.next === t) return head
  }
};