Easy to understand with O(n) time and O(1) space in Java


  • 0
    L
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
    	private ListNode findMiddle(ListNode head) {
    		if (head == null) return null;
    		ListNode slow = head;
    		ListNode fast = head.next;
    		while (fast != null && fast.next != null){
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}
    	private ListNode reverse(ListNode head) {
    		ListNode prev = null;
    		while(head != null){
    			ListNode temp = head.next;
    			head.next = prev;
    			prev = head;
    			head = temp;
    		}
    		return prev;
    	}
     public boolean isPalindrome(ListNode head) {
        	if (head == null) return true;
        	ListNode middle = findMiddle(head);
        	middle.next = reverse(middle.next);
        	ListNode p1 = head;
        	ListNode p2 = middle.next;
        	while (p1 != null && p2 != null && p1.val == p2.val ) {
    			p1 = p1.next;
    			p2 = p2.next;
    		}
        	return p2 == null;
        }
    }
    

    this idea comes from here:jiuzhang


Log in to reply
 

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