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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseList(self, head):
8 prev = None
9 current = head
10 while current:
11 nxt = current.next
12 current.next = prev
13 prev = current
14 current = nxt
15 return prev
16
17 def isPalindrome(self, head):
18 if not head or not head.next:
19 return True
20 slow = fast = head
21 while fast and fast.next:
22 slow = slow.next
23 fast = fast.next.next
24 second_half = self.reverseList(slow)
25 first_half = head
26 while second_half:
27 if first_half.val != second_half.val:
28 return False
29 first_half = first_half.next
30 second_half = second_half.next
31 return TrueThe Python solution follows the same approach of reversing the second half of the list and then comparing it with the first half to check for palindrome characteristics.
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.