I’ve been working a lot with the Linked List lately, and I thought I’d try a more practical problem today.

Problem

Given a singly linked list, determine if it is a palindrome.

As a follow up, the question also mentions:

Could you do it in O(n) time and O(1) space?

Solution

Funnily enough, despite being marked as an ‘Easy’ problem, the acceptance rate on this question is quite low, 30.5%. palindrome

So let’s break down the approach. We are using a singly linked list, and are not given the size of the Linked List. The only fields are the value, and the next node. The starting code provided by the question is below:

public class Solution {
    public boolean isPalindrome(ListNode head) {
        
    }
}

I’ll use this basic approach:

  • Get the half-way point of the list.
  • Reverse the second half of the list.
  • Compare the two halves.

I can reverse the list by using two pointers, one of which will move 2 nodes at a time, while the other moves 1. If we check when the faster ptr reaches the end, then the slower ptr will be at the half.

while (fastPtr.next != null && fastPtr.next.next != null ) {
    slowPtr = slowPtr.next;
    fastPtr = fastPtr.next.next;
}

Step one is done, now time to reverse the second half of the list. This is a singly linked list, so we will need to use three pointers to achieve this.

prev will point to the previous node. curr will point to the current node. nextBuffer will point to the next node.

  • We will store the next node in nextBuffer.
  • Because we are reversing, we will then set the next value in curr to the value of prev, which will initially be null.
  • We will then set prev to curr, when we increment curr, then prev will accurately represent the previous node.
  • Finally, we increment curr by setting it the value of the nextBuffer which we set in step 1.
    LinkedListNode curr = slowPtr;
    LinkedListNode nextBuffer = null;
    LinkedListNode prev = null;

    while (curr != null) {
        nextBuffer = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextBuffer;
    }

Step two done! Now it’s just a matter of comparing the two halves. The head pointer represents the first half of the list, while the prev pointer contains the second, reversed, half of the list.

while (prev != null && head != null) {
    if (head.data != prev.data) {
        return false;
    }

    head = head.next;
    prev = prev.next; 
}

The final (submitted) solution is below:

public class Solution {
	public boolean isPalindrome(ListNode head) {
		
		if (head == null || head.next==null) {
			return true;
		}

		ListNode slowPtr = head; // slowPtr will end at the half node
		ListNode fastPtr = head; // fastPtr will end at the last node

		while (fastPtr.next != null && fastPtr.next.next != null ) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}

		ListNode curr = slowPtr;
		ListNode nextBuffer = null;
		ListNode prev = null;

		while (curr != null) {
			nextBuffer = curr.next;
			curr.next = prev;
			prev = curr;
			curr = nextBuffer;
		}
		
		while (prev != null && head != null) {
			if (head.val != prev.val) {
				return false;
			}
			head = head.next;
			prev = prev.next; 
		}
		
		return true;

	}
}

submission

All the test cases passed, but only beating 34.92% of other Java submissions isn’t anything to brag about…. 2ms is quite slow.

The alternatives to my solution are a stack-based solution, and a recursive solution. All of these have O(n) time complexity, but could very well be much quicker.

Thanks for reading.