234. Palindrome Linked List Easy

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

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

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

Approach

Input: A linked list head

Output: Determine whether the linked list is a palindrome linked list

This problem belongs to the Fast and Slow Pointers category.

Stack Solution

We can use a stack to store the data of the nodes in the first half, and then, starting from the midpoint, compare whether the front and back are symmetrical.

To determine if a linked list is a palindrome, we have two situations:

• If the length of the list is odd, then the left and right sides must be symmetrical excluding the middle node.
• If the length of the list is even, then the left and right sides must be completely symmetrical.

We can find the midpoint position using fast and slow pointers:

• Both fast and slow pointers start from head.
• If the length is even, the fast pointer will reach None.
• If the length is odd, the fast pointer will stop at the last node. You can quickly verify this with 1 / 2 nodes.

While the slow pointer is traversing, we use a stack to record the nodes of the first half.

If the length of the linked list is odd, we need to move the slow pointer one more step to skip the middle node.

After that, the slow pointer traverses the second half and compares it one by one with the first half from the stack. If a difference is found, return false; otherwise, it is a palindrome linked list.

Reversal Solution

We can also reverse the second half of the linked list after finding the midpoint, get the tail node, and then simultaneously compare it with the head to see if they are symmetrical.

Implementation

Stack Solution

python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # Use a stack to save the node values of the first half
        stack = []
        slow, fast = head, head

        # Fast and slow pointers to find the midpoint, slow moves 1 step, fast moves 2 steps
        while fast and fast.next:
            stack.append(slow.val)  # Push the value of the first half into the stack
            slow = slow.next
            fast = fast.next.next

        # If the length of the list is odd, skip the middle node
        if fast:
            slow = slow.next

        # Compare the second half of the linked list with the values in the stack (reversed first half)
        while slow:
            if stack.pop() != slow.val:
                return False
            slow = slow.next

        return True

javascript

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let slow = head;
    let fast = head;
    const stack = [];

    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    if (fast) {
        slow = slow.next;
    }

    while (slow) {
        if (slow.val !== stack.pop()) {
            return false;
        }
        slow = slow.next;
    }

    return true;
};

Reversal Solution

python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # Fast and slow pointers finding mid (slow moves 1 step, fast moves 2 steps)
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half of the linked list
        def reverse(node):
            prev = None
            while node:
                nxt = node.next
                node.next = prev
                prev = node
                node = nxt
            return prev

        second_half = reverse(slow)  # Note: slow points to the midpoint, reverse it and the parts after it

        # Compare if the first half and the reversed second half are identical
        first, second = head, second_half
        while second:  # second is shorter (second half)
            if first.val != second.val:
                return False
            first = first.next
            second = second.next

        # (Optional) Restore the linked list structure
        # reverse(second_half)

        return True

javascript

function reverse(node) {
    let prev = null;
    let curr = node;

    while (node) {
        const nxt = node.next;
        node.next = prev;
        prev = node;
        node = nxt;
    }

    return prev;
}
var isPalindrome = function(head) {
    let slow = head;
    let fast = head;
    const stack = [];

    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    let secondHalf = reverse(slow);
    let curr = head;

    while (secondHalf) {
        if (curr.val !== secondHalf.val) {
            return false;
        }

        curr = curr.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) for Stack solution, O(1) for Reversal solution

Links

234. Palindrome Linked List (English)

234. 回文链表 (Chinese)