Leetcode discuss: 234. Palindrome Linked List

 April 25, 2022

Here is the link. 

C# | Optimal solution O(N) time complexity O(1) space

April 25, 2022
Introduction
It is important to learn optimal solution from Leetcode premium solution. I came cross the optimal solution and idea from here.

Optimal solution ideas | StefanPochmann
Solution 1: Reversed first half == Second half?

Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.

Leetcode premium discuss
Approach 3: Reverse Second Half In-place
Intuition

The only way we can avoid using O(n)O(n) extra space is by modifying the input in-place.

The strategy we can use is to reverse the second half of the Linked List in-place (modifying the Linked List structure), and then comparing it with the first half. Afterwards, we should re-reverse the second half and put the list back together. While you don't need to restore the list to pass the test cases, it is still good programming practice because the function could be a part of a bigger program that doesn't want the Linked List broken.

Algorithm

Specifically, the steps we need to do are:

1. Find the end of the first half.
2. Reverse the second half.
3. Determine whether or not there is a palindrome.
4. Restore the list.
5. Return the result.

To do step 1, we could count the number of nodes, calculate how many nodes are in the first half, and then iterate back down the list to find the end of the first half. Or, we could do it in a single parse using the two runners pointer technique. Either is acceptable, however we'll have a look at the two runners pointer technique here.

Imagine we have 2 runners one fast and one slow, running down the nodes of the Linked List. In each second, the fast runner moves down 2 nodes, and the slow runner just 1 node. By the time the fast runner gets to the end of the list, the slow runner will be half way. By representing the runners as pointers, and moving them down the list at the corresponding speeds, we can use this trick to find the middle of the list, and then split the list into two halves.

If there is an odd-number of nodes, then the "middle" node should remain attached to the first half.

Step 2 uses the algorithm that can be found in the solution article for the Reverse Linked List problem to reverse the second half of the list.

Step 3 is fairly straightforward. Remember that we have the first half, which might also contain a "middle" node at the end, and the second half, which is reversed. We can step down the lists simultaneously ensuring the node values are equal. When the node we're up to in the second list is null, we know we're done. If there was a middle value attached to the end of the first list, it is correctly ignored by the algorithm. The result should be saved, but not returned, as we still need to restore the list.

Step 4 requires using the same function you used for step 2, and then for step 5 the saved result should be returned.

Things to argue | end of first half | Why it is better to choose end of first half?
It is interesting to learn that function design is to find end of first half node instead of the first node in second half. I will think about more later.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _234_palindrom_linked_list
{
    class Program
    {
        public class ListNode {
            public int val;
            public ListNode next;
            public ListNode(int val=0, ListNode next=null) {
                this.val = val;
                this.next = next;
            }
        }

        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Code review:
        /// Study code: premium Leetcode solution 
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public bool IsPalindrome(ListNode head)
        {
            if (head == null)
            {
                return true;
            }

            // Find the end of first half and reverse second half.
            var firstHalfEnd = endOfFirstHalf(head);
            var secondHalfStart = reverseList(firstHalfEnd.next);

            // Check whether or not there is a palindrome.
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;

            bool result = true;

            while (result && p2 != null)
            {
                if (p1.val != p2.val) result = false;
                p1 = p1.next;
                p2 = p2.next;
            }

            // Restore the list and return the result.
            firstHalfEnd.next = reverseList(secondHalfStart);
            return result;
        }

        // Taken from https://leetcode.com/problems/reverse-linked-list/solution/
        private ListNode reverseList(ListNode head)
        {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null)
            {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }

            return prev;
        }

        /// <summary>
        /// using two pointers - one fast, one slow
        /// if the length of linked list is odd, then return ?
        /// if the length of linked list is even, then return ?
        /// 1 -> 2 -> 3 -> 4
        /// return second node with value 2
        /// 1 -> 2 -> 3 -> 4 -> 5
        /// return third node with value 3
        /// The node in the linked list is the first half end, make sure that it is correct
        /// in the above two test cases. 
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        private ListNode endOfFirstHalf(ListNode head)
        {
            ListNode fast = head;
            ListNode slow = head;

            // check if fast's next two steps - null pointer 
            while (fast.next != null && fast.next.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
            }

            return slow;
        }
    }
}