[LeetCode] #234 Palidrome LinkedList (repeat : 1)

Description 

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example1

 

Input : head = [1,2,2,1]
Output : true 

 

Example2 

 

Input : head = [1,2]

Output : false 

---

Solution 

class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode slow = head, fast = head, prev, temp;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        prev = slow;
        slow = slow.next;
        prev.next = null; // ends the connection

        while (slow != null) {
            temp = slow.next; // temp stores the node next to the slow 
            slow.next = prev; //slow.next points to the previous node (** reversing occurs)
            prev = slow; // prev moves to the slow poision 
            slow = temp; // slow moves to the next position 
        }

        fast = head; // fast is at head node
        slow = prev; /// slow is at tail node

        while (slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}

 

 

I wrote about the floyds tortois and hare algorithm in my blog

https://bytepudding.tistory.com/40

[Algorithms] 플로이드의 토끼와 거북이(Floyd's tortoise and hare)

 

what I kept missing was the second while loop's condition . slow starts from the end of the linkedlist but why 'slow != null' ?

it is because of the condition i set before 'prev.next = null' which means slow.next ends at the middle of the linkedlist. so when it is slow != null , slow traverses till the end of the linkedlist.