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 <iostream>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10ListNode* reverseList(ListNode* head) {
11 ListNode* prev = NULL;
12 ListNode* current = head;
13 while (current != NULL) {
14 ListNode* nextNode = current->next;
15 current->next = prev;
16 prev = current;
17 current = nextNode;
18 }
19 return prev;
20}
21
22bool isPalindrome(ListNode* head) {
23 if (head == NULL || head->next == NULL) return true;
24 ListNode* slow = head;
25 ListNode* fast = head;
26 while (fast != NULL && fast->next != NULL) {
27 slow = slow->next;
28 fast = fast->next->next;
29 }
30 ListNode* second_half = reverseList(slow);
31 ListNode* first_half = head;
32 while (second_half != NULL) {
33 if (first_half->val != second_half->val) return false;
34 first_half = first_half->next;
35 second_half = second_half->next;
36 }
37 return true;
38}In this C++ solution, we also reverse the second half of the list and compare it with the first half. The use of pointers allows us to efficiently manage the linked list nodes within the constraints provided.
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.
This C solution creates an array as large as the linked list to store values, which are then checked for palindromic order using two index pointers.