Might be the easiest Java solution to understand and is this O(n) time and O(1) space?


  • 0
    T

    I came up with this very basic approach, pretty similar with checking palindrome number.
    It is just my first try and it works.

    Please tell me where I could improve the code and is this the solution that costs O(n) time and O(1) space?

    Explanations:

    1. Find the middle of the list and break the list into two pieces
    2. Reverse the second half of the list
    3. Check if very node is the same in same position of each list.
    4. Since the number of nodes might be odd or even, so the last "if"
      checks are meant to deal with two different situations.

    public boolean isPalindrome(ListNode head) {
        if(head==null) {
            return true;
        }
        ListNode l1 = head;
        ListNode nodeBeforeMid = findMid(head);
        ListNode l2 = nodeBeforeMid.next;
        nodeBeforeMid.next = null;
        l2 = reverseList(l2);
        while(l1!=null && l2!=null && l1.val==l2.val) {
            l1 = l1.next;
            l2 = l2.next;
        }
        if(l1==null && l2==null) {
            return true;
        }
        else if(l1==null && l2!=null) {
            return true;
        }
        return false;
    }
    
    public ListNode findMid(ListNode head) {
        ListNode slow = new ListNode(0);
        slow.next = head;
        ListNode fast = new ListNode(0);
        fast.next = head;
        while(fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    public ListNode reverseList(ListNode head) {
        ListNode nHead = null;
        while(head!=null) {
            ListNode temp = head.next;
            head.next = nHead;
            nHead = head;
            head = temp;
        }
        return nHead;
    }

Log in to reply
 

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