分隔链表

参考官方的解法：直观来说我们只需维护两个链表 small 和 large 即可，small 链表按顺序存储所有小于 xxx 的节点，large 链表按顺序存储所有大于等于 xxx 的节点。遍历完原链表后，我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。

var partition = function (head, x) {
  let small = new ListNode(0)
  const smallHead = small
  let large = new ListNode(0)
  const largeHead = large

  while (head !== null) {
    if (head.val < x) {
      small.next = head
      small = small.next
    } else {
      large.next = head
      large = large.next
    }
    head = head.next
  }

  large.next = null
  small.next = largeHead.next

  return smallHead.next
}

备注：链表的题发现会先创建一个空节点，然后以此开始处理链接将节点加入到这个新的链表中，最后返回这个链表的头节点的下一个节点。

参考

• 86. 分隔链表 - 力扣（LeetCode） (opens new window)