Partition List

Description

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution(javascript)

// 分别记录两个列表
const partition = function (head, x) {
  let low = null
  let lowTail = null
  let high = null
  let highTail = null
  let current = head
  while (current) {
    if (current.val < x) {
      if (lowTail) {
        lowTail.next = current
        lowTail = current
      } else {
        low = current
        lowTail = current
      }
    } else if (highTail) {
      highTail.next = current
      highTail = current
    } else {
      high = current
      highTail = current
    }
    current = current.next
  }
  if (!low) {
    return high
  }
  if (highTail) {
    highTail.next = null
  }
  lowTail.next = high
  return low
}