Solution by vickyg3


  • 1
    V

    Approach #1 Brute Force (with extra n space) [Accepted]

    Intuition

    The simplest idea is to store a copy fo the linked list in an array and then compare if it is a palindrome by doing a linear scan over the array from both the ends.

    Algorithm

    Copy the linked list into an ArrayList<> and then compare them in a single loop.

    Java

    public class Solution {
        public boolean isPalindrome(ListNode head) {
            List<Integer> list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
            int i = 0;
            int j = list.size() - 1;
            while (i < j) {
                if (!list.get(i++).equals(list.get(j--))) return false;
            }
            return true;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    We run through the linked list once and then the array list once, resulting in 2n scans and thereby a time complexity of $$O(n)$$.

    • Space complexity : $$O(n)$$

    We use an extra Array of size exactly n.


    Approach #2 Brute Force (with extra n/2 space) [Accepted]

    Intuition

    This approach is similar to the one above, except that we don't have to store all of the n elements in the array. It is sufficient to store just the second half of the linked list in the array.

    Algorithm

    Find the middle element of the linked list, and copy the rest of the linked list into an array. Compare the first half the linked list traversing forward with the array traversing backward.

    The middle element of the linked list can be found with a two pointer approach. slow pointer moves one step forward in each iteration. fast pointer moves two steps in each iteration. Since the fast pointer moves twice as fast as the slow pointer, when the fast pointer reaches the end of the list, the slow pointer will point to the middle.

    Java

    public class Solution {
        private ListNode findMiddle(ListNode head) {
              ListNode slow = head;
              ListNode prevSlow = head;
              ListNode fast = head;
              while (fast != null) {
                  prevSlow = slow;
                  slow = slow.next;
                  if (fast.next != null) {
                      fast = fast.next.next;
                  } else {
                      fast = null;
                  }
              }
              prevSlow.next = null;
              return slow;
          }
    
          public boolean isPalindrome(ListNode head) {
              if (head == null || head.next == null) return true;
              ListNode mid = findMiddle(head);
              List<Integer> list = new ArrayList<>();
              while (mid != null) {
                  list.add(mid.val);
                  mid = mid.next;
              }
              int i = list.size() - 1;
              while (head != null) {
                  if (head.val != list.get(i--).intValue()) return false;
              }
              return true;
          }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    We run through the linked list once and then the half of the array and the linked list once, resulting in 2n scans and thereby a time complexity of $$O(n)$$.

    • Space complexity : $$O(n)$$

    We use an extra Array of size exactly n/2.


    Approach #3 Reverse the second half in-place [Accepted]

    Intuition

    The key realization about this problem is that the second half of the list as-is cannot be traversed backward in linear time since it is a singly linked list. So we can simply reverse the second half of the list (which can be done in linear time). Once we do that, it is just a matter of comparing both lists to check for palindrome.

    Algorithm

    Find the middle element of the linked list. Reverse the linked list starting from the middle element. Now, merely compare both the lists and check if it is a palindrome.

    Reversing a singly linked list can be done in linear time. You need 3 pointers p1, p2 and p3 pointing to adjacent nodes. You can then make p2.next point to p1 since you have it stored in p3. You can then go on reversing the rest of the list by moving all three pointers forward by one step.

    Java

    public class Solution {
        private ListNode findMiddle(ListNode head) {
              ListNode slow = head;
              ListNode prevSlow = head;
              ListNode fast = head;
              while (fast != null) {
                  prevSlow = slow;
                  slow = slow.next;
                  if (fast.next != null) {
                      fast = fast.next.next;
                  } else {
                      fast = null;
                  }
              }
              prevSlow.next = null;
              return slow;
          }
    
          private ListNode reverse(ListNode head) {
              ListNode p1 = head;
              ListNode p2 = head.next;
              ListNode p3;
              p1.next = null;
              while (p2 != null) {
                  p3 = p2.next;
                  p2.next = p1;
                  p1 = p2;
                  p2 = p3;
              }
              return p1;
         }
    
         public boolean isPalindrome(ListNode head) {
             if (head == null || head.next == null) return true;
             ListNode mid = reverse(findMiddle(head));
             while (mid != null) {
                 if (mid.val != head.val) return false;
                 mid = mid.next;
                 head = head.next;
             }
             return true;
         }     
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    We run through the linked list once to find the middle. We then reverse the second half of the list in one run through it. The final step is the comparison of the two half-lists resulting in ~3n scans and thereby a time complexity of $$O(n)$$.

    • Space complexity : $$O(1)$$

    We do not use any extra space.


Log in to reply
 

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