JAVA solution O(n)/O(1) while reconstructing original list


  • 0
    L

    While the naming is still messy at some partsand I know I can improve the code by reversing the first half while calculating the mid pointer, I am feeling lazy to do that. Here is my solution which reverses the second half and reconstructs to original list when finished.

    /**
     * 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 || head.next == null) {
                return true;
            }
    
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
    
            ListNode newHead = slow.next;
            slow.next = null;
            ListNode reversedHead = reverse(newHead);
            
            ListNode mid = slow;
            slow = head;
            fast = reversedHead;
            while(slow!=null && fast!=null) {
                if (slow.val != fast.val) {
                    break;
                }
    
                slow = slow.next;
                fast = fast.next;
            }
    
            newHead = reverse(reversedHead);
            mid.next = newHead;
    
            if (fast!=null) {
                return false;
            }
    
            return true;
        }
    
        private ListNode reverse(ListNode head) {
            if (head == null) {
                return null;
            }
    
            ListNode prev = null;
            ListNode cur = head;
            while(cur != null) {
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }
    
            return prev;
        }
    }
    

Log in to reply
 

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