Problem statement

Given the head of a singly linked list, return true if its values read the same from front to back as from back to front, and false otherwise.

Example 1

Input: head = [1,2,2,1]
Output: true

Example 2

Input: head = [1,2]
Output: false

Example 3

Input: head = [3,0,3]
Output: true
Explanation: An odd-length palindrome: the middle value is compared with nothing.

Constraints

• The number of nodes in the list is in the range [1, 10^5]
• 0 <= Node.val <= 9

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

Hints for Palindrome Linked List

1. Hint 1

   Copying the values into an array and checking it with two indices works, but costs O(n) space.

2. Hint 2

   With a slow and a fast pointer you can find the middle in one pass — and the slow pointer can reverse the first half as it goes.

3. Hint 3

   Once the first half is reversed, walk it and the second half side by side (skip the middle node when the length is odd) and compare.

How to solve Palindrome Linked List

A palindrome's first half, reversed, equals its second half. Find the middle with slow/fast pointers while reversing the links of the first half on the way, then compare the two halves node by node — no extra memory.

Approach

1. Set slow = fast = head, prev = null.
2. While fast and fast.next exist: advance fast two steps; then move slow one step forward, reversing its link to point at prev (save slow.next first).
3. If fast is not null the length is odd: step slow past the middle node.
4. Now prev heads the reversed first half and slow the second half. Walk both together; any differing pair means false.
5. If they all match, return true.

Why it works

When fast reaches the end, slow has moved floor(n / 2) times, so exactly the first half has been reversed into prev. Reading prev forward gives the first half backwards, which must equal the second half read forward for a palindrome.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Odd lengths: the middle node belongs to neither half — skip it.
• Advance fast before relinking slow, or the reversal can cut the path fast needs.
• This modifies the list; restore it by reversing again if the caller needs it intact.

Reference solution

Python

from typing import Optional

def isPalindrome(head: Optional[ListNode]) -> bool:
    slow = fast = head
    prev = None
    while fast and fast.next:
        fast = fast.next.next
        nxt = slow.next
        slow.next = prev
        prev, slow = slow, nxt
    if fast:
        slow = slow.next  # odd length: skip the middle
    while prev:
        if prev.val != slow.val:
            return False
        prev, slow = prev.next, slow.next
    return True

Java

public static boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    if (fast != null) slow = slow.next; // odd length: skip the middle
    while (prev != null) {
        if (prev.val != slow.val) return false;
        prev = prev.next;
        slow = slow.next;
    }
    return true;
}

C++

bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head, *prev = nullptr;
    while (fast && fast->next) {
        fast = fast->next->next;
        ListNode* next = slow->next;
        slow->next = prev;
        prev = slow;
        slow = next;
    }
    if (fast) slow = slow->next; // odd length: skip the middle
    while (prev) {
        if (prev->val != slow->val) return false;
        prev = prev->next;
        slow = slow->next;
    }
    return true;
}

JavaScript

var isPalindrome = function(head) {
    var slow = head, fast = head, prev = null;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        var next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    if (fast !== null) slow = slow.next; // odd length: skip the middle
    while (prev !== null) {
        if (prev.val !== slow.val) return false;
        prev = prev.next;
        slow = slow.next;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Nth Node From End of Linked List Easy
• Intersection of Two Sorted Linked Lists Easy
• Middle of the Linked List Easy
• Remove Duplicates from Sorted List Easy
• Merge Two Sorted Lists Easy
• Two Sum IV - Input is a BST Easy