Unique solution which creates two numbers that are reverse of each other


  • 0
    T

    I found this unique solution which works by generating two numbers that would be the reverse of each other.
    In a simple case such as [1,2,3] the numbers would be 123 and 321.
    This works even if we have either very large numbers or have a very long linked list by overflowing the bounds on 32 bit integers. If the linked list is a palindrome, both the generated numbers would overflow the bounds of integer in the same way and the final generated values would be the same.
    I didn't see anyone else list this solution either in this forum or in my search on the web. I'm a bit excited to have found a unique solution. Please leave a comment if you see any problems with this solution or if you have any thoughts. Thanks!

    //Author: Tushar Jaiswal
    //Creation Date: 03/25/2017
    
    /*Given a singly linked list, determine if it is a palindrome.
    Follow up: Could you do it in O(n) time and O(1) space?*/
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public bool IsPalindrome(ListNode head) {
            int a = 0, b = 0, i = 0;
            while(head != null)
            {
                a = 10 * a + head.val;
                if(i == 0)
                {
                    b = head.val + b;
                    i = 1; 
                }
                else
                {
                    i *= 10;
                    b = i * head.val + b;
                }
                head = head.next;
            }
            return a == b;
        }
    }
    

Log in to reply
 

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