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

Follow up:

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

/**
* Definition for singly-linked list.
* public class ListNode {
*   int val;
*   ListNode next;
*   ListNode(int x) { val = x; }
* }
*/
public class Solution {
  public boolean isPalindrome(ListNode head) {
      
  }
}

This problem is selected from LeetCode.

Solution

As we could only use constant extra space, the only solution is to compare the first half and the second half of the linked list node by node. That means we need to reverse the first half of the list, and then compare them.

To reverse only the first half of the list, we could use a fast and a slow pointer. The fast pointer each time steps two nodes in the list. The slow pointer each time steps one node in the list. When the fast pointer reaches the end, the slow pointer is at the middle node. While moving the slow pointer, we could reverse the node right away. After that, we could compare the two halves node by node.

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

  ListNode start = new ListNode(0);
  start.next = head;
  ListNode firstHalfStart = head;
  ListNode secondHalfStart = head;
  ListNode fast = head;

  // find the starting points of the first half and
  // the second half. Reverse the first half right away.
  while(fast.next != null && fast.next.next != null) {
    fast = fast.next.next;

    start.next = secondHalfStart.next;
    secondHalfStart.next = secondHalfStart.next.next;
    start.next.next = firstHalfStart;

    firstHalfStart = start.next;
  }
  secondHalfStart = secondHalfStart.next;

  // odd number of elements, need to left 
  // move firstHalfStart one step
  if(fast.next == null) {
    firstHalfStart = firstHalfStart.next;
  }
  
  //compare from mid to head/tail
  while(secondHalfStart != null) {
    if(firstHalfStart.val != secondHalfStart.val)
      return false;
      
    secondHalfStart = secondHalfStart.next;
    firstHalfStart = firstHalfStart.next;
  }
  return true;
}

RelatedPost