143. Reorder List

Link: https://leetcode.com/problems/reorder-list

Description: Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

Solution:

1. Find the Middle of the Linked List: Use the fast and slow pointer technique. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.
2. Reverse the Second Half of the List: After finding the middle, reverse the second part of the list starting from the middle to the end. This can be achieved by standard linked list reversal techniques.
3. Merge the Two Halves: Start from the head of the first half and the head of the reversed second half. Alternate nodes from each part to achieve the desired order.

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

  // Step 1: Find the middle of the linked list
  let slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }

  // Step 2: Reverse the second half of the list
  let prev = null,
    curr = slow,
    tmp
  while (curr) {
    tmp = curr.next
    curr.next = prev
    prev = curr
    curr = tmp
  }

  // Step 3: Merge the two halves
  let first = head,
    second = prev
  while (second.next) {
    tmp = first.next
    first.next = second
    first = tmp

    tmp = second.next
    second.next = first
    second = tmp
  }
}