O(n) speed, O(1) space concise Java solution with explanation.


  • 0
    M

    This solution is in place and only one pass, the main idea is reverse the first half of the linked list, find the mid start point, then compare with the original start point. For the reverse part, you may take "Reverse Linked List II"'s code as an example.

    public class Solution {
                public boolean isPalindrome(ListNode head) {
                    if(head == null || head.next == null) return true;
                    ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
                    dummy.next = head;
                    ListNode then = head.next;
                    ListNode fast = head.next.next;
                    while (fast != null && fast.next != null) {
                        //reverse the first half of the linked list
                        then = head.next;
                        head.next = then.next;
                        then.next = dummy.next;
                        dummy.next = then;
                        fast = fast.next.next;
                    }
                    //jump one more step if the node amount is odd
                    if(fast != null) head = head.next;
                    ListNode newHead = dummy.next;
                    ListNode midHead = head.next;
                    while(midHead != null){
                        if(newHead.val != midHead.val) return false;
                        newHead = newHead.next;
                        midHead = midHead.next;
                    }
                    return true;
                }
            }

Log in to reply
 

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