[LeetCode] Palindrome Linked List

This is classic leetcode problem: https://leetcode.com/problems/palindrome-linked-list/

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

Simple solution is to go through the linked list, and put all node reference on a stack, then loop through the stack and linked list at the same time to compare the values. 

public boolean isPalindrome(ListNode head) {
        Stack<Integer> s = new Stack<>();
        ListNode n = head;
        while(n!=null){
            s.push(n.val);
            n = n.next;
        }
        while(head!=null){
            if(head.val != s.pop())
                return false;
            head = head.next;    
        }
        return true;
    }

Follow up:
Could you do it in O(n) time and O(1) space?
This can be done by reversing the half of the linked list. First of all, we need to find the middle point of the list, then reverse the second half, and compare the first half from head and second half from the tail. 

	public class Solution {
	public boolean isPalindrome(ListNode head) {
	//use two pointers with different paces to find the middle point
	ListNode slow = head, fast = head;
	while(fast!=null && fast.next!=null){
	slow = slow.next;
	fast = fast.next.next;
	}
	//if there are even node except 2, here
	//fast will be null, slow will be point to the exact node
	//from there we will reverse
	//otherwise fast will be not null, slow will be point to the
	//middle point, and we will move it one step further
	if(fast!=null)
	slow = slow.next;
	//ok, let's reverse from slow to tail, and return tail
	//here we use two pointers, p and next
	//and set next.next to p
	ListNode p = slow, next = null;
	if(p!=null){
	next = p.next;
	//remember to set the first node.next to null
	slow.next = null;
	}
	while(p!=null && next!=null){
	ListNode nextnext = next.next;
	next.next = p;
	//move p and next along
	p = next;
	next = nextnext;
	}
	ListNode tail = p;
	//now we have two linked lists
	while(tail!=null && head!=null){
	if(tail.val!=head.val)
	return false;
	head = head.next;
	tail = tail.next;
	}
	return true;
	}
	}

view raw palindrome-linked-list.java hosted with ❤ by GitHub