2ms Very Simple Java Solution with explanation


  • 3
    J
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            ListNode dummy = new ListNode(10);
            dummy.next = head;
            if(head == null) return true;
            ListNode slow = head;         
            ListNode fast = head.next;
            //Find the middle node
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //Reverse the last half of the linked list
            ListNode pre = null;
            slow = slow.next;
            while(slow != null){
                ListNode temp = slow.next;
                slow.next = pre;
                pre = slow;
                slow = temp;
            }
            //Compare two linked lists
            head = dummy.next;
            while(head != null && pre != null){
                if(head.val != pre.val) return false;
                head = head.next;
                pre = pre.next;
            }
            return true;
        }
    }

Log in to reply
 

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