[LeetCode] 234. Palindrome Linked List

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

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

Thought process:

Use a fast and a slow pointer to iterate through the list. At the end, slow is at the middle of the list and fast is at the end. Reverse the second half of the list. Iterate through both halves in the same time and check if they match.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if (head == null) { return true; } ListNode mid = getMid(head); ListNode midReversed = reverse(mid); while (midReversed != null) { if (head.val != midReversed.val) { return false; } head = head.next; midReversed = midReversed.next; } return true; } private ListNode getMid(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow.next; } private ListNode reverse(ListNode head) { ListNode previous = null; while (head != null) { ListNode next = head.next; head.next = previous; previous = head; head = next; } return previous; } }

Time complexity: O(n).