This is our given problem,

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

Example 1:

```Input: 1->2
Output: false```

Example 2:

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

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,

1. Slow and Fast Pointer Approach

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

1. Slow pointer moves by one position
2. Fast pointer moves by two positions
``````Consider the below example,

//slow = 1->2-1->2->1->null

//slow = 1->2-1->2->1->null

//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;

fast = 1->2->null;``````

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

## Solution

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {

while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}

//odd node
if(fast != null)
{
slow = slow.next;
}

slow = reverse(slow);

while(slow != null)
{
if(slow.val != fast.val)
{
return false;
}
slow =  slow.next;
fast = fast.next;
}
return true;
}

{
{
}
}
}
```

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.

Processing…
Success!