重排链表

Tips

题目类型: LinkedList

相关题目:

• 206. 反转链表
• 876. 链表的中间结点

题目

给定一个单链表 L 的头节点 head, 单链表 L 表示为:

L₀ → L₁ → ... → L_{n - 1} → L_n

请将其重新排列后变为:

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 2} → ...

示例

输入: head = [1, 2, 3, 4]

输出: [1, 4, 2, 3]

输入: head = [1, 2, 3, 4, 5]

输出: [1, 5, 2, 4, 3]

题解

该题为 206. 反转链表 + 876. 链表的中间结点 + 21. 合并两个有序链表的组合体.

/**
 * 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) return null

  const mid = findMiddleNode(head)
  let l1 = head
  let l2 = mid.next
  // 防止循环引用
  mid.next = null
  l2 = reverseLinkedList(l2)
  mergeLinkedList(l1, l2)
}

var findMiddleNode = function (head) {
  let fast = head
  let slow = head

  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
  }

  return slow
}

var reverseLinkedList = function (head) {
  let prev = null
  // 注意不要直接使用 head, 而是浅拷贝一个引用
  let curr = head

  while (curr) {
    const tmp = curr.next
    curr.next = prev
    prev = curr
    curr = tmp
  }

  return prev
}

var mergeLinkedList = function (l1, l2) {
  while (l1 && l2) {
    const l1_tmp = l1.next
    const l2_tmp = l2.next

    l1.next = l2
    l1 = l1_tmp

    l2.next = l1
    l2 = l2_tmp
  }
}