Java O(n) time, O(1) Space


  • 0
    X

    If O(n) space , just reverse list to another list (list2), and compare them.
    If O(1) space, you have to reverse the list in half and compare them , so find the middle is the key point.
    Here is my code, I destroy the list ,but you can rebuild it very easily

    public class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while( fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode left = head;
        ListNode right = reverse(slow.next);
        while(right != null ){
            if(left.val != right.val ){
                return  false;
        }
        left = left.next;
        right = right.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode node){
        if(node == null){
            return node;
        }
        ListNode pre = node;
        ListNode cur = node.next;
        node.next = null;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    

    }


Log in to reply
 

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