Question

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?

Solution

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        if (head.next.next == null) {
            return head.val == head.next.val;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverse(slow.next);

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

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

Execution time: 2 ms, defeated 94.13% of users in the Java submission of the Palindrome Linked List

Memory consumption: 42.8 MB, 80.45% of users in the Java submission of the Palindrome Linked List

Related Companies

• Adobe
• Apple
• Alibaba
• Baidu
• ByteDance
• DiDi
• Xiaomi
• Microsoft
• Tencent
• IXL
• Uber
• Wangyi