Checking Palindrome in a Singly Linked List
Mon Mar 11 2024 checkPalindrome:
Method within a LinkedList class to determine if a singly linked list is a palindrome. The approach involves reversing the second half of the list and then comparing it with the first half. If all corresponding nodes in the two halves are equal, the list is a palindrome. This technique effectively utilizes fast and slow pointers to identify the midpoint of the list, reverses the second half in-place, and conducts a node-by-node comparison to verify the palindrome property without extra space.
1class Node {
2 constructor(data) {
3 this.data = data;
4 this.next = null;
5 }
6}
7
8class LinkedList {
9 constructor() {
10 this.head = null;
11 }
12
13 addLast(data) {
14 const newNode = new Node(data);
15 if (!this.head) {
16 this.head = newNode;
17 } else {
18 let current = this.head;
19 while (current.next) {
20 current = current.next;
21 }
22 current.next = newNode;
23 }
24 }
25
26 reverse() {
27 if (!this.head) return null;
28 let prevPointer = null;
29 let currentPointer = this.head;
30 let nextPointer;
31 while (currentPointer) {
32 nextPointer = currentPointer.next;
33 currentPointer.next = prevPointer;
34 prevPointer = currentPointer;
35 currentPointer = nextPointer;
36 }
37 return prevPointer;
38 }
39
40 checkPalindrome() {
41 if (!this.head || !this.head.next) {
42 return true;
43 }
44
45 let slow = this.head;
46 let fast = this.head;
47
48 while (fast.next && fast.next.next) {
49 slow = slow.next;
50 fast = fast.next.next;
51 }
52
53 slow.next = this.reverse(slow.next);
54 let firstHalf = this.head;
55 let secondHalf = slow.next;
56
57 while (secondHalf && firstHalf) {
58 if (firstHalf.data !== secondHalf.data) {
59 return false;
60 }
61 firstHalf = firstHalf.next;
62 secondHalf = secondHalf.next;
63 }
64 return true;
65 }
66}
67
68const linkedlist = new LinkedList();
69linkedlist.addLast(9);
70linkedlist.addLast(10);
71linkedlist.addLast(9);
72console.log(linkedlist.checkPalindrome());
73
74const linkedlist1 = new LinkedList();
75linkedlist1.addLast(10);
76linkedlist1.addLast(10);
77linkedlist1.addLast(9);
78console.log(linkedlist1.checkPalindrome());
79