LeetCode Palindrome Linked List: O(1) Space

Overview

LeetCode Palindrome Linked List: use slow/fast pointers O(1) to get the middle of linked list, reverse the right half, compare reversed half and the left

LeetCode Palindrome Linked List

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

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

LeetCode Palindrome Linked List Solution: O(1) Space

The trivial solution is to allocate another array, copy the linked list into that array, and use head/tail index to compare the sequence, take a look at these two posts to know what palindrome exactly is and how to validate the basic palindrome string or number: LeetCode Valid Palindrome: O(N) Time and O(1) Space with Two PointersLeetCode Palindrome Number: No Extra Space. Also, another easy way would be still using linked list, but we can reverse the original list while keeping a second copy of the old linked list, and scan them to compare.

In order to save the O(N) space, we only need the compare the left half and the right half of the linked list, so it could be achieved by:

  1. use slow/faster pointers to get the middle node of the linked list and thus determine the head of the right half linked list
  2. reverse the right half linked list
  3. compare the left and right reversed half linked list, it is a palindrome linked list if and only if these two sub-linked list are the same.
  4. if required, we need to reverse the right half again to reconstruct back the original linked list

The following Java code implemented it in O(N) time and O(1) space, and it is accepted by LeetCode OJ to pass this Palindrome Linked List problem:

/**
 * 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) {
        if (head == null ||
            head.next == null) {
	    return true;
	}

	ListNode s, f;
	s = head;
        f = head;

	while (f != null &&
               f.next != null) {
	    f = f.next.next;
	    s = s.next;
	}

	if (f != null) {
            s = s.next;
	}

	ListNode l = head;
	ListNode r = reverse(s);

	while (r != null) {
	    if (l.val != r.val) {
	        return false;
            }
	    l = l.next;
	    r = r.next;
	}

	return true;
    }

    private ListNode reverse(ListNode l) {
	if (l == null ||
            l.next == null) {
	    return l;
	}

	ListNode p1 = l,
                 p2 = l.next,
                 p3 = p2.next;

	l.next = null;
	while (p2 != null) {
	    p3 = p2.next;
	    p2.next = p1;
	    p1 = p2;
	    p2 = p3;
	}

	return p1;
    }

}

Note to reverse the linked list, you could also so it in iterative way or in recursive way, take a look at this post for further reference: LeetCode Reverse Linked List: Recursive VS Iterative Solution

Summary

LeetCode Palindrome Linked List: use slow/fast pointers O(1) to get the middle of linked list, reverse the right half, compare reversed half and the left

Written on July 14, 2015