Given a singly Linked List, determine if it is a Palindrome

Technology CommunityCategory: Linked ListsGiven a singly Linked List, determine if it is a Palindrome
VietMX Staff asked 1 year ago
Problem

Could you do it in O(1) time and O(1) space?

Solution: is Reversed first half == Second half?

Let’s look to an example [1, 1, 2, 1]. In the beginning, set two pointers fast and slow starting at the head.

1 -> 1 -> 2 -> 1 -> null
sf

(1) Move: fast pointer goes to the end, and slow goes to the middle.

1 -> 1 -> 2 -> 1 -> null
          s          f

(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

1 -> 1    null <- 2 <- 1
h                      s

(3) Compare: run the two pointers head and slow together and compare.

1 -> 1    null <- 2 <- 1
     h            s
Implementation
public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast != null) { // odd nodes: let right half smaller
        slow = slow.next;
    }
    slow = reverse(slow);
    fast = head;
    
    while (slow != null) {
        if (fast.val != slow.val) {
            return false;
        }
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}