86. 分隔链表

方式一

function partition(head: ListNode | null, x: number): ListNode | null {
  if (!head) {
    return null
  }

  let current = head // 当前遍历原始链表的位置
  let lessDummy = new ListNode() // 按照顺序存放小于的值
  let greaterDummy = new ListNode() // 按照顺序存放大于的值

  let less = lessDummy // 小于的链表的末尾
  let greater = greaterDummy // 大于的链表的末尾

  while (current) {
    if (current.val < x) {
      less.next = current
      less = less.next
    } else {
      greater.next = current
      greater = greater.next
    }

    current = current.next
  }

  less.next = greaterDummy.next // 将小于和大于的链表连接起来
  greater.next = null // 避免后面还有小于的值造成循环

  return lessDummy.next
}

方式二

方式一需要结束后将 greater.next 置为 null，因为 greater 处理完后可能最终的 greater 后面跟着的是小于的值，这样的话就会形成循环

如果每次追加结点都将 next 置为 null，那么处理结束后的链表就不需要额外处理了

function partition(head: ListNode | null, x: number): ListNode | null {
  if (!head) {
    return null
  }

  let current = head // 当前遍历原始链表的位置
  let lessDummy = new ListNode() // 按照顺序存放小于的值
  let greaterDummy = new ListNode() // 按照顺序存放大于的值

  let less = lessDummy // 小于的链表的末尾
  let greater = greaterDummy // 大于的链表的末尾

  while (current) {
    if (current.val < x) {
      less.next = current
      less = less.next
    } else {
      greater.next = current
      greater = greater.next
    }

    // 手动将接上来的结点的 next 断掉
    // 避免后面形成循环指针
    const temp = current.next
    current.next = null
    current = temp
  }

  less.next = greaterDummy.next // 将小于和大于的链表连接起来

  return lessDummy.next
}