Leetcode discuss: 234. Palindrome Linked List

April 25, 2022

Here is the link. 

C# | Review of my practice in July 2018

April 25, 2022
Introduction
I like to review my practice in July 2018. In order to determine if the linked list has palindrome feature, with O(N) time complexity and O(1) space.

Get length of linked list | O(N) time complexity
I wrote a function to get linked list length. Is it possible to solve the problem without getting length of linked list?

I also wrote a function to reverse a linked list. I do believe that the optimal solution may not need to save a copy of linked list using reversed order, which is not O(1) space.

Better solution | Code review
I like to write a solution using reverse first half of linked list, and then find middle point of linked list, compare first half and next half. The idea can be implemented using O(N) time and O(1) space complexity.

I do think that it is important to learn a few ideas and try a few things. Make a few mistakes, and I will learn much fast.

The following C# code passes online judge.

public class Solution {
    public bool IsPalindrome(ListNode head)
        {
            if (head == null)
                return true;

            if (head.next == null)
                return true;

            var length = getLinkedListLength(head);
            var isEven = length % 2 == 0;
            var back = head;
            var front = getNodeGivenK(head, length/ 2);
            if (!isEven)
            {
                front = front.next;
            }
            
            var reversed = reverseLinkedList(front);

            // compare two linked list one element a time 
            var index = 0;
            while (index < length / 2)
            {
                if (back.val != reversed.val)
                    return false;

                back = back.next;
                reversed = reversed.next;
                index++;
            }

            return true;
        }

        /// <summary>
        /// reverse a linked list using O(N) time and O(1) space
        /// </summary>
        /// <param name="head"></param>
        private static ListNode reverseLinkedList(ListNode head)
        {
            if (head == null)
                return null;
            if (head.next == null)
                return head;

            var next = head.next;
            var reversed = reverseLinkedList(next);

            head.next = null;
            next.next = head;

            return reversed;
        }

        private static ListNode getNodeGivenK(ListNode head, int k)
        {
            if (k == 0)
                return head;

            int index = 0;
            var iterate = head;
            while (index < k)
            {
                iterate = iterate.next;
                index++;
            }

            return iterate;
        }

        private static int getLinkedListLength(ListNode head)
        {
            if (head == null)
                return 0;

            var index = 0; 
            var iterate = head;
            while (iterate != null)
            {
                index++;

                iterate = iterate.next;
            }

            return index; 
        }
}