Palindrome Linked List

easy linked list two pointers

Problem

Return true if the singly linked list reads the same forward and backward. Solve in O(n) time and O(1) extra space.

Inputhead = 1 → 2 → 2 → 1

Outputtrue

Find the middle, reverse the second half, then compare with the front half pair-by-pair.

values (comma-separated)

def isPalindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev, slow = slow, nxt
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null;
  while (slow) {
    const nxt = slow.next;
    slow.next = prev;
    prev = slow; slow = nxt;
  }
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next; right = right.next;
  }
  return true;
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        ListNode prev = null;
        while (slow != null) {
            ListNode nxt = slow.next;
            slow.next = prev;
            prev = slow; slow = nxt;
        }
        ListNode left = head, right = prev;
        while (right != null) {
            if (left.val != right.val) return false;
            left = left.next; right = right.next;
        }
        return true;
    }
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head; ListNode* fast = head;
        while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
        ListNode* prev = nullptr;
        while (slow) {
            ListNode* nxt = slow->next;
            slow->next = prev;
            prev = slow; slow = nxt;
        }
        ListNode* left = head; ListNode* right = prev;
        while (right) {
            if (left->val != right->val) return false;
            left = left->next; right = right->next;
        }
        return true;
    }
};

Explanation

To check a palindrome in constant extra space, we do it in three moves: find the middle, reverse the second half, then walk the two halves toward each other comparing values.

First the fast/slow pointers find the middle: fast moves two steps while slow moves one, so when fast ends, slow sits at the start of the second half. Then we reverse that second half in place using the usual prev / nxt pointer flip, leaving prev as the new head of the reversed back half.

Finally we compare: left walks from the original head and right walks from prev. If every pair of values matches until right runs out, the list is a palindrome. Any mismatch returns false early.

Example: 1 → 2 → 2 → 1. The middle splits it into front 1 → 2 and back 2 → 1; reversing the back gives 1 → 2. Comparing front vs reversed back: 1=1, 2=2, so it returns True.

Because we only relink nodes and use a handful of pointers, this checks the list in linear time without an extra array.

Time: O(n) Space: O(1)