Fast C# solution. O(1) memory. O(n) runtime.


  • 0
    N

    0_1473133554465_upload-162388cf-bb5d-49e1-b638-d1da2067a298

    public class Solution {
    public bool IsPalindrome(ListNode head)
    {
    if (head == null || head.next == null)
    {
    return true;
    }
    // find the middle of the list and split the list in two
    ListNode secondHalf = Split(head);

        // reverse the last half of the list
        secondHalf = ReverseList(secondHalf);
    
        ListNode firstHalf = head;
        // compare the begining of the the list to the second half.
        while (firstHalf != null) 
        {
            if(firstHalf.val != secondHalf.val)
            {
                return false;
            }
    
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
    
        }
    
        return true;
    }
    
    private ListNode Split(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head.next;
        int iterationCount = 0;
        while(fast != null)
        {
            if (fast.next == null)
            {
                ListNode temp = slow.next;
                slow.next = null;
                return temp;
            } 
    
            if (fast.next.next == null)
            {
                ListNode temp = slow.next.next;
                if (iterationCount % 2 == 0)
                {
                    slow.next = null;
                } else
                {
                    slow.next.next = null;
                }
    
                return temp;
            }
    
            slow = slow.next; // 1x
            fast = fast.next.next; // 2x
        }
    
        return null;
    }
    
    // performs an in place re-ordering of the list
    public ListNode ReverseList(ListNode head)
    {
        if(head == null || head.next == null)
        {
            return head;
        }
    
        ListNode previous = null;
        ListNode current = head;
        ListNode next = head.next;
    
        while (next != null)
        {
            ListNode temp = next.next;
    
            // reverse the direction of the links
            next.next = current;
            current.next = previous;
    
            // move the pointers
            previous = current;
            current = next;
            next = temp;
        }
    
        return current;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.