1class Node {
2  constructor(data) {
3    this.data = data;
4    this.next = null;
5  }
6}
7
8class LinkedList {
9  constructor(data) {
10    this.head = null;
11  }
12  addFirst(data) {
13    const newNode = new Node(data);
14    newNode.next = this.head;
15    this.head = newNode;
16  }
17  size() {
18    let count = 0;
19    if (!this.head) return count;
20
21    let current = this.head;
22    while (current) {
23      count++;
24      current = current.next;
25    }
26    return count;
27  }
28  print() {
29    let current = this.head;
30    while (current) {
31      console.log(current.data);
32      current = current.next;
33    }
34  }
35}
36
37class QuickSortLinkedList extends LinkedList {
38  sort() {
39    this.head = this.quickSort(this.head, this.getPivot(this.head));
40  }
41
42  getPivot(node) {
43    while (node && node.next) {
44      node = node.next;
45    }
46    return node;
47  }
48
49  partition(head, end) {
50    let pivot = end.data;
51    let prev = null,
52      tail = end,
53      current = head;
54
55    while (current !== end && current != null) {
56      if (current.data < pivot) {
57        if (prev === null) {
58          head = current;
59        } else {
60          prev.next = current;
61        }
62        prev = current;
63      } else {
64        tail.next = current;
65        tail = current;
66      }
67      current = current.next;
68    }
69    tail.next = null;
70    if (prev !== null) {
71      prev.next = end;
72    }
73    return head;
74  }
75
76  quickSort(start, end) {
77    if (start == null || start === end) {
78      return start;
79    }
80
81    let partitioned = this.partition(start, end),
82      pivot = start;
83
84    while (pivot != null && pivot.next != null && pivot.next != end) {
85      pivot = pivot.next;
86    }
87
88    if (pivot != null && pivot.next == end) {
89      pivot.next = null;
90    }
91
92    let newStart = null;
93    if (partitioned != end) {
94      newStart = this.quickSort(partitioned, pivot);
95
96      if (pivot != null) {
97        pivot.next = end;
98      }
99    }
100
101    if (end != null && end.next != null) {
102      end.next = this.quickSort(end.next, this.getPivot(end.next));
103    }
104
105    return newStart == null ? start : newStart;
106  }
107}
108
109const sortedLinkedList = new QuickSortLinkedList();
110
111sortedLinkedList.addFirst(3);
112sortedLinkedList.addFirst(13);
113sortedLinkedList.addFirst(8);
114sortedLinkedList.addFirst(5);
115sortedLinkedList.addFirst(2);
116
117sortedLinkedList.sort();
118sortedLinkedList.print();
119