Sponsored
Sponsored
This approach involves reversing the second half of the linked list and then comparing it with the first half. If they are identical, the linked list is a palindrome. The steps include:
Time Complexity: O(n) since we are traversing the list multiple times but each in linear time.
Space Complexity: O(1) as we are reversing the linked list in place.
1function ListNode(val, next = null) {
2 this.val = val;
3 this.next = next;
4}
5
6function reverseList(head) {
7 let prev = null;
8 let current = head;
9 while (current !== null) {
10 let nextNode = current.next;
11 current.next = prev;
12 prev = current;
13 current = nextNode;
14 }
15 return prev;
16}
17
18function isPalindrome(head) {
19 if (!head || !head.next) return true;
20 let slow = head;
21 let fast = head;
22 while (fast !== null && fast.next !== null) {
23 slow = slow.next;
24 fast = fast.next.next;
25 }
26 let secondHalf = reverseList(slow);
27 let firstHalf = head;
28 while (secondHalf !== null) {
29 if (firstHalf.val !== secondHalf.val) {
30 return false;
31 }
32 firstHalf = firstHalf.next;
33 secondHalf = secondHalf.next;
34 }
35 return true;
36}JavaScript solution implements the same principle of reversing the second half of the list, followed by comparing it with the first half.
In this approach, convert the linked list into an array and utilize a two-pointer technique to determine if it forms a palindrome. The steps are as follows:
Time Complexity: O(n) due to single traversation and subsequent O(n/2) check.
Space Complexity: O(n) because we store all node values in an array.
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public bool IsPalindrome(ListNode head) {
List<int> values = new List<int>();
ListNode current = head;
while (current != null) {
values.Add(current.val);
current = current.next;
}
int left = 0, right = values.Count - 1;
while (left < right) {
if (values[left] != values[right]) return false;
left++;
right--;
}
return true;
}
}C# List is employed to store linked list values before a two-pointer check thoroughly verifies if the stored sequence forms a palindrome.