Check if a given linked list is Palindrome or not

Problem: Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example:

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

Approach: We can use a Stack and push all the nodes in it and then we can compare each and every node from head to top of stack and if all nodes values match then we can say the list is palindrome. Basically we are comparing list's reverse with it but it will take O(n) extra space. Let's reduce it:

Go to the middle node of linked list and then reverse all the nodes after the middle element. Now we can compare all the nodes' value from head to middle node's next value (basically the start node of the reversed list). If all matches, we can say the list is palindrome. We can get the middle element in one pass using slow and fast pointer approach which we have used in finding loop in linked list. Let's see using the above example:

1->2->3->2->1

Now 3 is middle element so we will reverse the list 2->1, so now the list will become:

1->2->3->1->2

Now lets say assign 2 iterators one it1 to head and second itr2 to next of middle. Now we will compare all these nodes till itr2 becomes null. You can see it will return true as all the nodes' value actually matches.

Implementation in C#:

    public bool IsPalindrome(ListNode head)

    {

        ListNode slow = head;

        ListNode fast = head.next;

        while (fast?.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        ListNode itr1 = head;

        ListNode itr2 = this.ReverseFromNode(slow.next);

        while (itr2 != null)

        {

            if (itr1.val != itr2.val)

            {

                return false;

            }

            itr1 = itr1.next;

            itr2 = itr2.next;

        }

        return true;

    }

    private ListNode ReverseFromNode(ListNode node)

    {

        ListNode prev = null, curr = node;

        while (curr != null)

        {

            ListNode next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

        return prev;

    }

Complexity: O(n)