1class Node {
2  constructor(val) {
3    this.data = val;
4    this.next = null;
5  }
6}
7
8class LinkedList {
9  constructor() {
10    this.head = null;
11  }
12  addLast(val) {
13    const newNode = new Node(val);
14    if (!this.head) {
15      this.head = newNode;
16      return;
17    }
18
19    let current = this.head;
20    while (current.next) {
21      current = current.next;
22    }
23    current.next = newNode;
24    return;
25  }
26
27  segregateEvenOdd() {
28    let end = this.head;
29    let prev = null;
30    let current = this.head;
31    while (end.next !== null) {
32      end = end.next;
33    }
34
35    let newEnd = end;
36    while (current.data % 2 !== 0 && current !== end) {
37      newEnd.next = current;
38      current = current.next;
39      newEnd.next.next = null;
40      newEnd = newEnd.next;
41    }
42
43    while (current !== end) {
44      if (current.data % 2 === 0) {
45        if (prev) {
46          prev.next = current;
47        } else {
48          this.head = current;
49        }
50        prev = current;
51        current = current.next;
52      } else {
53        prev.next = current.next;
54        newEnd.next = current;
55        current.next = null;
56        newEnd = current;
57        current = prev.next;
58      }
59      if (newEnd !== end && end.data % 2 !== 0) {
60        prev.next = end.next;
61        newEnd.next = end;
62        end.next = null;
63      }
64    }
65  }
66  print() {
67    let current = this.head;
68    while (current) {
69      console.log(current.data);
70      current = current.next;
71    }
72  }
73}
74const linkedlist = new LinkedList();
75linkedlist.addLast(17);
76linkedlist.addLast(15);
77linkedlist.addLast(8);
78linkedlist.addLast(9);
79linkedlist.addLast(2);
80linkedlist.addLast(4);
81linkedlist.addLast(6);
82
83// linkedlist.print();
84linkedlist.segregateEvenOdd();
85linkedlist.print();
86