Palindrome

Implement a function to check if a linked list is a palindrome.

👉 Link here to the repo to solve the problem

👌 Tips

A palindrome is something which is the same when written forwards and backwards. What if you reversed the linked list?

Try using a stack.

Assume you have the length of the linked list. Can you implement this recursively?

👊 Solution 1

As we know a palindrome is just the same frontwards and backwards, one easy to implement approach would be to reverse the list values and compare them. This is a nice implementation as we can break down each step onto a separate function. The runtime would be of O(N).

    public static boolean linkedListPalindromeReverseAndCompare(SingleLinkedListNode node) {
           SingleLinkedListNode reversed = reverseList(node);
            return compareLists(node, reversed);
    }

    private static boolean compareLists(SingleLinkedListNode n1, SingleLinkedListNode n2) {
        while (n1 != null) {
            if (n1.data != n2.data) return false;
            n1 = n1.next;
            n2 = n2.next;
        }
        return true;
    }

👊 Solution 2

One approach to do this is to use a stack to keep track of the elements in the linked list up to the halfway point. We ignore the middle node if the list has an odd length. Then we start popping from the stack after the halfway point and see if the node values are same until we reach the end of the list.

The tricky part is to find the half way point. In a singly linked list, we cannot easily access it's length without traversing the whole list and we also can't traverse backwards. This is where the runner technique would be really useful. There are two cases we have to handle (odd or even length list). The following visualization explains the runner technique in action.

Odd length list

1	2	3	4	5
S	S	S
F		F		F

Even length list

1	2	3	4	5	6	NULL
S	S	S	S
F		F		F		F

As you can see, if we use the runner technique the slow pointer will always end up in the middle of the list. The only issue here is when the list is odd in length which we simply just ignore the middle node by pointing the slow pointer to it's next node. We know that the list is odd in length if the fast pointer is not null (as shown in the visualization above).

public boolean isPalindrome(Node head) {
  if (head.next == null) return false;

  Node slow = head;
  Node fast = head;
  Stack<Integer> stack = new Stack<>();

  while (fast != null && fast.next != null) {
    stack.push(slow.data);
    slow = slow.next;
    fast = fast.next.next;
  }

  // When list had odd length, simply ignore the middle node
  if (fast != null) slow = slow.next;

  while (slow != null) {
    if (stack.pop() != slow.data) return false;
    slow = slow.next;
  }

  return true;
}

---

Question borrowed from “Cracking the coding interview”