1
function getListSize(head) {
2
  let curr = head;
3
  let size = 0;
4

5
  while (curr !== null) {
6
    size += 1;
7

8
    curr = curr.next;
9
  }
10

11
  return size;
12
}
13

14
function splitInHalf(head, n) {
15
  let node1 = head;
16
  let curr = head;
17

18
  for (let i = 0; i < Math.floor(n / 2) - 1; i++) {
19
    curr = curr.next;
20
  }
21

22
  const node2 = curr.next;
23
  curr.next = null;
24

25
  return [node1, Math.floor(n / 2), node2, n - Math.floor(n / 2)];
26
}
27

28
function merge(head1, head2) {
29
  if (head1.val > head2.val) {
30
    return merge(head2, head1);
31
  }
32

33
  const head = head1;
34
  let curr = head1;
35

36
  let runner1 = curr.next;
37
  let runner2 = head2;
38

39
  while (runner1 !== null || runner2 !== null) {
40
    const runner1Value = runner1 ? runner1.val : Infinity;
41
    const runner2Value = runner2 ? runner2.val : Infinity;
42

43
    if (runner1Value < runner2Value) {
44
      curr.next = runner1;
45
      runner1 = runner1.next;
46
    } else {
47
      curr.next = runner2;
48
      runner2 = runner2.next;
49
    }
50

51
    curr = curr.next;
52
  }
53

54
  curr.next = null;
55
  return head;
56
}
57

58
var sortList = function (head) {
59
  const size = getListSize(head);
60

61
  function mergeSort(node, n) {
62
    if (n <= 1) {
63
      return node;
64
    }
65

66
    const [node1, n1, node2, n2] = splitInHalf(node, n);
67
    const [merged1, merged2] = [mergeSort(node1, n1), mergeSort(node2, n2)];
68

69
    return merge(merged1, merged2);
70
  }
71

72
  return mergeSort(head, size);
73
};