2 Java AC Solutions: Iterative and Recursive


  • 2
    J

    Iterative Solution:

    1. Split the list into two halfs
    2. Reverse the second half
    3. Compare the first half and second half
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            
            ListNode preMid = findPreMid(head);
            ListNode head2 = reverse(preMid.next);
            preMid.next = null;
            
            while (head != null && head2 != null) {
                if (head.val != head2.val) {
                    return false;
                }
                
                head = head.next;
                head2 = head2.next;
            }
            
            return true;
        }
        
        public ListNode reverse(ListNode head) {
            ListNode pre = null;
            ListNode cur = head;
            
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            
            return pre;
        }
        
        public ListNode findPreMid(ListNode head) {
            ListNode slow = head;
            ListNode fast = head.next;
            
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            return slow;
        }
    }
    

    Recursive Solution:

    public class Solution {
        ListNode cur;
        
        public boolean isPalindrome(ListNode head) {
            cur = head;
            return helper(head);
        }
        
        public boolean helper(ListNode head) {
            if (head == null) {
                return true;
            }
            
            boolean flag = helper(head.next);
            
            if (flag && head.val == cur.val) {
                cur = cur.next;
                return true;
            }
            
            return false;
        }
    }

  • 0
    L

    You can't reverse using recursion because it must be O(1) space. Using recursion to reverse the second half will consume O(n/2) space.


  • 0
    J

    I didn't reverse the list using recursion. The first solution is iterative


Log in to reply
 

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