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 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 private ListNode reverseList(ListNode head) {
9 ListNode prev = null;
10 while (head != null) {
11 ListNode nextNode = head.next;
12 head.next = prev;
13 prev = head;
14 head = nextNode;
15 }
16 return prev;
17 }
18
19 public boolean isPalindrome(ListNode head) {
20 if (head == null || head.next == null) {
21 return true;
22 }
23 ListNode slow = head, fast = head;
24 while (fast != null && fast.next != null) {
25 slow = slow.next;
26 fast = fast.next.next;
27 }
28 ListNode secondHalf = reverseList(slow);
29 ListNode firstHalf = head;
30 while (secondHalf != null) {
31 if (firstHalf.val != secondHalf.val) {
32 return false;
33 }
34 firstHalf = firstHalf.next;
35 secondHalf = secondHalf.next;
36 }
37 return true;
38 }
39}Here, the Java solution involves reversing the second half of the linked list. The reversal and comparison steps efficiently determine if the list is a palindrome.
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.