Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 1: Palindrome LinkedList

Problem Statement

Given the head of a Singly LinkedList, write a method to check if the LinkedList is a palindrome or not.

Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished. The algorithm should have O(N) time complexity where ‘N’ is the number of nodes in the LinkedList.

Example 1:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> null
Output: true

Example 2:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> 2 -> null
Output: false

Constraints:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Santosh Vaza

· 4 years ago

No need to check head != null (refer to the attached image)

because in 1st case (1st underline in image) headSecondHalf will exhaust sooner than the head itself, since headSecondHalf is reversed, there is no way where the head will exhaust before headSecondHalf.

In 2nd case, we can confirm its palindrome when headSecondHalf is null so there is no need to check head==null as well. Image

A

Avinash Agarwal

· 4 years ago

This does not look like it reverts the head to its original form. For input [1,2,2,2,1] head: null slow: [2,2,1] fast: [1] headSecondHalf: null copyHeadSecondHalf: [1]

Show 2 replies
T

Thilak G

· 4 years ago

The second half becomes its own linked list and the reverse back at the end does not put the linked list to it's original state ?

2 -> 4

Second half Null

Show 1 reply
A

Aditya Verma

· 3 years ago

For add length the code might not work. Correct solution is: package com.techsavvy;

public class PalindromeLinkedlIst {

public static void main(String[] args) {

	ListNode head = new ListNode(2);

	head.next = new ListNode(4);

	head.next.next = new ListNode(6);

	head.next.next.next = new ListNode(8);

	head.next.next.next.next = new ListNode(6);

	head.next.next.next.next.next = new ListNode(4);

	head.next.next.next.next.next.next = new ListNode(2);

	if(*isPalindome*(head)) {

		System.*out*.println("Given List is Palindrome");

	} else {

		System.*out*.println("Given list is not a Palindrome");

	}

}



private static int length(ListNode head) {

	int count = 0;

	while(head != null) {

		head = head.next;

		count++;

	}

	return count;

}



private s
S

Santosh Vaza

· 3 years ago

Check the solution here.

Show 2 replies
adi berkowitz

adi berkowitz

· 2 years ago

#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def isPalindrome(self, head):
    if head and head.next is None:
      return True
    slow, fast = head, head
    prev = slow
    # Classic fast and slow to get to middle of list
    while fast and fast.next:
      prev = slow
      slow = slow.next
      fast = fast.next.next
    # If fast is not None, that means list is odd and we can ignore the middle number
    # (ie: 1, 2, 3, 2, 1) -> we could ignore 3
    if fast:
      slow = slow.next
    # We do this because we don't care about anything after first half and we already have pointer to second half
    prev.next = None
    # reverse from slow on
    current = slow
    reverse = None
    # This is how to
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next
class Solution:
  def isPalindrome(self, head):
    
    def find_mid_node(head):
      slow, fast = head, head
      while fast:
        if fast.next:
          fast = fast.next.next
        else:
          break
        slow = slow.next
      mid = slow
      return mid
    
    def reverse_linked(node, stop):
      prev = None
      while node != stop:
        next_ = node.next
        node.next = prev
        prev = node
        node = next_
      return prev

    def check_palindrome(first, mid, last):
      is_palindrome = True
      while first and last and (first != mid or last != mid):
        if first.val != last.val:
          is_palindrome = False
          break
R

Ricardo Estrada

· 2 years ago

Problem description has the following constraint:

  • 1 <= Node.val <= 9

Although one of the test cases contains a 10 within the array.

Michał Sabiniarz

Michał Sabiniarz

· 2 years ago

Please correct me if I'm wrong but to me it looks like the code for isPalindrome could be simpler. If I'm wrong please supply me a test for which it would fail


class Solution:
    def isPalindrome(self, head):
        mid = self.find_mid(head)
        reversed = self.reverse(mid)
        
        node = head
        original_reversed_head = reversed
        while reversed:
            if reversed.val != node.val:
                return False
            reversed = reversed.next
            node = node.next

        # Restore linked list
        self.reverse(original_reversed_head)

        return True



    def find_mid(self, head):
        slow, fast = head, head
        while fast and fast.next:
            # Slow goes one step
            slow = slow.next
            # Fast