Question
Formatted question description: https://leetcode.ca/all/234.html
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?
@tag-linkedlist
Algorithm
The principle of using fast and slow pointers to find the midpoint,each time the fast pointer moves two steps and the slow pointer moves one step. When the fast pointer finishes, the position of the slow pointer is the midpoint.
After finding the midpoint, flip the linked list in the second half to compare in the order of palindrome.
Code
Java
public class Palindrome_Linked_List {
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
// 2 pointers to find mid
ListNode slowPrev = new ListNode(0);
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slowPrev = slow;
slow = slow.next;
}
// now slow aat middle
slowPrev.next = null; // cut
ListNode reversed2ndHalf = reverseNodeList(slow);
ListNode p1 = head;
ListNode p2 = reversed2ndHalf;
while (p1 != null && p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
private ListNode reverseNodeList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode current = head;
while (current != null) {
ListNode currenHead = dummy.next;
ListNode nextHead = current.next;
current.next = null; // cut current node out
dummy.next = current;
current.next = currenHead;
current = nextHead;
}
return dummy.next;
}
}