728x90
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
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.
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode]#13. Roman to Integer (repeat : 0 ) (0) | 2024.01.22 |
---|---|
[LeetCode] #169. Majority Element (repeat : 0 ) (0) | 2024.01.21 |
[LeetCode] #92. Reverse Linked List II (repeat : 0) (0) | 2024.01.18 |
[LeetCode] #26. Remove Duplicates from Sorted Array (reapeat : 0) (0) | 2024.01.17 |
[LeetCode] #27. Remove Element (repeat : 0) (0) | 2024.01.16 |