Easy understand JAVA solution (O(1) space cost)


  • 58
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null) {
                return true;
            }
            ListNode p1 = head;
            ListNode p2 = head;
            ListNode p3 = p1.next;
            ListNode pre = p1;
            //find mid pointer, and reverse head half part
            while(p2.next != null && p2.next.next != null) {
                p2 = p2.next.next;
                pre = p1;
                p1 = p3;
                p3 = p3.next;
                p1.next = pre;
            }
    
            //odd number of elements, need left move p1 one step
            if(p2.next == null) {
                p1 = p1.next;
            }
            else {   //even number of elements, do nothing
                
            }
            //compare from mid to head/tail
            while(p3 != null) {
                if(p1.val != p3.val) {
                    return false;
                }
                p1 = p1.next;
                p3 = p3.next;
            }
            return true;
            
        }
    }

  • 2

    So you use p2 to locate the middle point as p2 moves at double speed of p1's. Cool!


  • 0

    Thanks for your appreciation!


  • 3
    B

    Reverse half a list can answer the follow up question. But it changes input, which is a bad solution in a practical project. I think we need to point it out during the interview.


  • 1

    Yes, I agree with you. Actually the code should reverse the list back when it doing the comparation. I'm too lazy to write it down. Sorry for this.


  • 0
    S
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    This post is deleted!

  • 4
    This post is deleted!

  • -1

    hahahhaahaha


  • 0
    K
    This post is deleted!

  • 11
    T

    People, please stop spamming. We understand you guys know each other and are excited about it but please reserve that for personal chats.

    Also, I found your variable (p1, p2, p3, etc.) naming a little confusing as an external reader.
    I found your approach very similar to what I implemented, so I'll paste it below:

    public boolean isPalindrome(ListNode head) {
        // Trivial case
        if(head == null || head.next == null) { return true;}
        
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode firstHalfStart = head;
        ListNode secondHalfStart = head;
        ListNode fast = head;
        
        // Traverse to mid node and Reverse the First half of the LinkedList in the same run
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            
            start.next = secondHalfStart.next;
            secondHalfStart.next = secondHalfStart.next.next;
            start.next.next = firstHalfStart;
            
            firstHalfStart = start.next;
        }
        
        // Offset for odd number of elements
        // As the mid node is common to both halves, this should be skipped
        if(fast.next == null) {
            firstHalfStart = firstHalfStart.next;
        }
        
        // At the end of the previous loop, SecondHalfStart pointer is still stuck on the end of the first half
        // Shift it by one to take it to the start of the SecondHalf
        secondHalfStart = secondHalfStart.next;
        
        while(secondHalfStart != null) {
            if(firstHalfStart.val != secondHalfStart.val) { return false;}
            secondHalfStart = secondHalfStart.next;
            firstHalfStart = firstHalfStart.next;
        }
        return true;
    }

  • 0
    L
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    M

    Can we really claim that no list is a palindrome? head == false no?


  • 0
    C
    This post is deleted!

  • 48

    An accepted concise version:

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
    
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast != null) slow = slow.next;
        
        slow = reverse(slow);
        while(slow != null && head.val == slow.val) {
            head = head.next;
            slow = slow.next;
        }
        return slow == null;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

Log in to reply
 

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