This is our given problem,

Given a singly linked list, determine if it is a palindrome.

**Example 1:**

Input:1->2Output:false

**Example 2:**

Input:1->2->2->1Output:true

**Follow up:**

Could you do it in O(n) time and O(1) space?

#### How can we APPROACH this problem?

By using two ways, we can solve this problem,

- Slow and Fast Pointer Approach
- Reversing the Linked List

If you do not know, how to reverse the linked list, I already made an article with clear explanation of how to reverse the linked list with both iterative and recursive approach.

### Slow and Fast Pointer Approach

- Slow pointer moves by one position
- Fast pointer moves by two positions

```
Consider the below example,
head = 1->2-1->2->1->null
slow = head;
//slow = 1->2-1->2->1->null
slow = head;
//slow = 1->2-1->2->1->null
fast = head;
//fast = 1->2-1->2->1->null
```

```
//iteration first time
while(fast != null && fast.next != null)
{
slow = slow.next;
//slow = 2-1->2->1->null
fast = fast.next.next;
//fast = 1->2->1->null
}
```

```
//iteration second time
while(fast != null && fast.next != null)
{
slow = slow.next;
//slow = 1->2->1->null
fast = fast.next.next;
//fast = 1->null
}
```

```
Since fast.next == null, it comes out of the while loop
Still now we have,
slow = 1->2->1->null;
fast = 1->null;
We have odd length of linked list, so that we have to ignore the middle node,
in this case, for slow = 1->2->1->null, ignore the 1st node,
```

How can we ignore that, move the slow pointer to the next position.

Note:

if fast == null, it means we have even length linked list

if fast != null, it means we have odd length linked list

```
if(fast != null)
{
slow = slow.next;
//slow = 2->1->null
}
Now reverse the slow linked list, then it becomes
slow => 1-2->null;
Assign head pointer to fast;
head = 1->2->null;
fast = 1->2->null;
```

Iterate one by one,

Compare each other, if it is not equal return false.

## Solution

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } //odd node if(fast != null) { slow = slow.next; } slow = reverse(slow); fast = head; while(slow != null) { if(slow.val != fast.val) { return false; } slow = slow.next; fast = fast.next; } return true; } public ListNode reverse(ListNode head) { ListNode newHead = null; while(head != null) { ListNode next = head.next; head.next = newHead; newHead = head; head = next; } return newHead; } }

Time Complexity : O(n)

Space Complexity: O(1)

**Note:**

Since I’m interested in problem-solving, so I love to teach others programming in a short and sweet way. To get notification of my future articles like this, follow me via email.