[leetcode - Bliend-75 ] 143. Reorder List (Medium)

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example

Input: 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Step

  // find the middle  let fast = head;  let slow = head;  while (fast.next?.next) {    slow = slow.next;    fast = fast.next.next;  }

将 linked list 由刚刚找的的中间 node 分为两个 linked list 并将右边的 linked list 反转

将左边的 linked list 和右边的 linked list 合併

Coding

/** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead.*/var reorderList = function (head) {  // find the middle  let fast = head;  let slow = head;  while (fast.next?.next) {    slow = slow.next;    fast = fast.next.next;  }  // reverse  let curr = slow.next;  slow.next = null;  let prev = null;  while (curr) {    let tmp = curr.next;    curr.next = prev;    prev = curr;    curr = tmp;  }  let h1 = head;  let h2 = prev;  while (h2) {    let tmp = h1.next;     h1.next = h2;    h1 = h2;    h2 = tmp;  }};

Time complexity: O(n)