Palindrome Linked List

LeetCode Q 234 - Palindrome Linked List

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

Example 1:
Input: 1->2 ; Output: false

Example 2:
Input: 1->2->2->1 ; Output: true

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

Solution :

Code:

public boolean isPalindrome(ListNode head) {
	if (head == null || head.next == null)
		return true;
	// step 1: find mid
	ListNode dummy = new ListNode(-1), slow = dummy, fast = dummy;
	dummy.next = head;
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	// step 2: reverse 2nd half
	ListNode head2 = reverse(slow.next);
	slow.next = null;
	
	// stop 3: compare 1st and 2nd halves
	ListNode curr = head, curr2 = head2;
	while (curr != null && curr2 != null && curr.val == curr2.val) {
		curr = curr.next;
		curr2 = curr2.next;
	}
	
	return curr2 == null;
}

private ListNode reverse(ListNode head) {
	ListNode node = null;
	while (head != null) {
		ListNode next = head.next;
		head.next = node;
		node = head;
		head = next;
	}
	return node;
}