#### 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 {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
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 {
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode prevSlow = head;
ListNode fast = head;
while (fast != null) {
prevSlow = slow;
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
fast = null;
}
}
prevSlow.next = null;
return slow;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode mid = findMiddle(head);
List<Integer> list = new ArrayList<>();
while (mid != null) {
list.add(mid.val);
mid = mid.next;
}
int i = list.size() - 1;
while (head != null) {
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 {
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode prevSlow = head;
ListNode fast = head;
while (fast != null) {
prevSlow = slow;
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
fast = null;
}
}
prevSlow.next = null;
return slow;
}
private ListNode reverse(ListNode head) {
ListNode p1 = head;
ListNode p2 = head.next;
ListNode p3;
p1.next = null;
while (p2 != null) {
p3 = p2.next;
p2.next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode mid = reverse(findMiddle(head));
while (mid != null) {
if (mid.val != head.val) return false;
mid = mid.next;
head = head.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.