Simple java solution with explanation


  • 3
    T
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null)
                return true;
                
            // reverse second half of list
            ListNode slow = head;
            ListNode fast = head;
            
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            ListNode prev = null;
            ListNode curr = slow;
            ListNode tmp;
            while (curr != null) {
                tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }
            
            // compare first half and reversed second list
            ListNode p1 = head, p2 = prev;
            while (p1 != null && p2 != null) {
                if (p1.val != p2.val)
                    return false;
                p1 = p1.next;
                p2 = p2.next;
            }
            
            return true;
        }
    }

Log in to reply
 

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