How to partition a linked list around a node with a certain value

JavaScript, algorithms, linked list

Here is one way to partition a linked list around a value x such that all nodes less than x comes before all nodes greater than or equal to x.

partitionTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function partition(node, x) {
    let head = node;
    let tail = node;
    
    while (node) {
        const next = node.next;
        if (node.data < x) {
            node.next = head;
            head = node;
        } else {
            tail.next = node;
            tail = node;
        }
        node = next;
    }
    tail.next = null;
    
    return head;
}
function Node(data) {
  this.next = null;
  this.data = data;
}
Node.prototype.addToTail = function(data) {
  const end = new Node(data);
  let current = this;
  while (current.next !== null) {
    current = current.next;
  }
  current.next = end;
  return end;
};

Tests can be found at REPL.it