# Solution by vickyg3

• #### Approach #1 Brute Force (with extra n space) [Accepted]

Intuition

The simplest idea is to store a copy fo the linked list in an array and then compare if it is a palindrome by doing a linear scan over the array from both the ends.

Algorithm

Copy the linked list into an ArrayList<> and then compare them in a single loop.

Java

``````public class Solution {
List<Integer> list = new ArrayList<>();
}
int i = 0;
int j = list.size() - 1;
while (i < j) {
if (!list.get(i++).equals(list.get(j--))) return false;
}
return true;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

We run through the linked list once and then the array list once, resulting in `2n` scans and thereby a time complexity of \$\$O(n)\$\$.

• Space complexity : \$\$O(n)\$\$

We use an extra Array of size exactly n.

#### Approach #2 Brute Force (with extra n/2 space) [Accepted]

Intuition

This approach is similar to the one above, except that we don't have to store all of the n elements in the array. It is sufficient to store just the second half of the linked list in the array.

Algorithm

Find the middle element of the linked list, and copy the rest of the linked list into an array. Compare the first half the linked list traversing forward with the array traversing backward.

The middle element of the linked list can be found with a two pointer approach. `slow` pointer moves one step forward in each iteration. `fast` pointer moves two steps in each iteration. Since the fast pointer moves twice as fast as the slow pointer, when the fast pointer reaches the end of the list, the slow pointer will point to the middle.

Java

``````public class Solution {
while (fast != null) {
prevSlow = slow;
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
fast = null;
}
}
prevSlow.next = null;
return slow;
}

List<Integer> list = new ArrayList<>();
while (mid != null) {
mid = mid.next;
}
int i = list.size() - 1;
if (head.val != list.get(i--).intValue()) return false;
}
return true;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

We run through the linked list once and then the half of the array and the linked list once, resulting in `2n` scans and thereby a time complexity of \$\$O(n)\$\$.

• Space complexity : \$\$O(n)\$\$

We use an extra Array of size exactly n/2.

#### Approach #3 Reverse the second half in-place [Accepted]

Intuition

The key realization about this problem is that the second half of the list as-is cannot be traversed backward in linear time since it is a singly linked list. So we can simply reverse the second half of the list (which can be done in linear time). Once we do that, it is just a matter of comparing both lists to check for palindrome.

Algorithm

Find the middle element of the linked list. Reverse the linked list starting from the middle element. Now, merely compare both the lists and check if it is a palindrome.

Reversing a singly linked list can be done in linear time. You need 3 pointers `p1`, `p2` and `p3` pointing to adjacent nodes. You can then make `p2.next` point to `p1` since you have it stored in `p3`. You can then go on reversing the rest of the list by moving all three pointers forward by one step.

Java

``````public class Solution {
while (fast != null) {
prevSlow = slow;
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
fast = null;
}
}
prevSlow.next = null;
return slow;
}

ListNode p3;
p1.next = null;
while (p2 != null) {
p3 = p2.next;
p2.next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}

while (mid != null) {
if (mid.val != head.val) return false;
mid = mid.next;
}
return true;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

We run through the linked list once to find the middle. We then reverse the second half of the list in one run through it. The final step is the comparison of the two half-lists resulting in `~3n` scans and thereby a time complexity of \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$

We do not use any extra space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.