Segregate even and odd nodes in a Linked List
Mon Mar 25 2024 segregateEvenOdd:
This ingenious function takes on the challenge by first traversing to the end of the list to identify the last node, setting the stage for rearrangement. It then iterates from the head, relocating odd nodes to the list's end while maintaining even nodes at the forefront. This is achieved through a series of pointer adjustments that ensure even nodes are linked together followed by the odd nodes, without disrupting the original order among them. Special attention is given to the list's start, ensuring the head points to the first even node if available, and to the end, carefully placing any remaining odd nodes without breaking the newly formed even-odd sequence.
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