2 ms Java, fast and slow pointer


  • 0
    N
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null){
                return true;
            }
            
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            
            ListNode sp = dummy;
            ListNode fp = dummy;
            
            while(fp.next != null && fp.next.next != null){
                sp = sp.next;
                fp = fp.next.next;
            }
            
            ListNode leftEnd = sp;
            if(fp.next != null){
                // odd list;
                sp = sp.next;
            }
            ListNode rightStart = sp.next;
            leftEnd.next = null;//cut
            
            ListNode left = dummy.next;
            reverse(left);
            
            while(leftEnd != null){
                if(leftEnd.val != rightStart.val){
                    return false;
                }
                else{
                    leftEnd = leftEnd.next;
                    rightStart = rightStart.next;
                }
            }
            return true;
        }
        
        public void reverse(ListNode head){
            ListNode cur = head.next;
            head.next = null;
            while(cur != null){
                ListNode next = cur.next;
                cur.next = head;
                head = cur;
                cur = next;
            }
        }
    }
    

Log in to reply
 

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