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.
1#include <stdbool.h>
2#include <stdio.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* reverseList(struct ListNode* head) {
10 struct ListNode* prev = NULL;
11 struct ListNode* current = head;
12 struct ListNode* next = NULL;
13 while (current != NULL) {
14 next = current->next;
15 current->next = prev;
16 prev = current;
17 current = next;
18 }
19 return prev;
20}
21
22bool isPalindrome(struct ListNode* head) {
23 if (head == NULL || head->next == NULL) return true;
24 struct ListNode* slow = head;
25 struct ListNode* fast = head;
26 while (fast != NULL && fast->next != NULL) {
27 slow = slow->next;
28 fast = fast->next->next;
29 }
30 struct ListNode* reversedSecondHalf = reverseList(slow);
31 struct ListNode* p1 = head;
32 struct ListNode* p2 = reversedSecondHalf;
33 while (p2 != NULL) {
34 if (p1->val != p2->val) return false;
35 p1 = p1->next;
36 p2 = p2->next;
37 }
38 return true;
39}The above solution in C reverses the second half of the linked list starting from the middle. We use a fast and slow pointer to find the middle together with reversing the second half and checking for equality.
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.