#234 Palindrome Linked List - Solution

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

Constraints:

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

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

Approach	Time Complexity	Space Complexity
Two Pointers + Reverse Second Half	O(n)	O(1)
Stack-Based Comparison	O(n)	O(n)
Recursive Comparison	O(n)	O(n)

Solutions (12)

Reverse Second Half and Compare

This approach involves reversing the second half of the linked list and then comparing it with the first half. If they are identical, the linked list is a palindrome. The steps include:

Use two pointers (slow and fast) to find the middle of the linked list.
Reverse the second half of the linked list.
Compare the first half and the reversed second half of the list.

Time Complexity: O(n) since we are traversing the list multiple times but each in linear time.
Space Complexity: O(1) as we are reversing the linked list in place.

C C++Java Python C#JavaScript

1#include <iostream>
2using namespace std;
3
4struct ListNode {
5    int val;
6    ListNode *next;
7    ListNode(int x) : val(x), next(NULL) {}
8};
9
10ListNode* reverseList(ListNode* head) {
11    ListNode* prev = NULL;
12    ListNode* current = head;
13    while (current != NULL) {
14        ListNode* nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (head == NULL || head->next == NULL) return true;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* second_half = reverseList(slow);
    ListNode* first_half = head;
    while (second_half != NULL) {
        if (first_half->val != second_half->val) return false;
        first_half = first_half->next;
        second_half = second_half->next;
    }
    return true;
}

Explanation

In this C++ solution, we also reverse the second half of the list and compare it with the first half. The use of pointers allows us to efficiently manage the linked list nodes within the constraints provided.

Convert to Array and Use Two Pointers

In this approach, convert the linked list into an array and utilize a two-pointer technique to determine if it forms a palindrome. The steps are as follows:

Traverse the linked list and store its elements in an array.
Use two pointers, one starting at the beginning and the other at the end of the array, to compare values.
If all corresponding elements are identical, the list is a palindrome.

Time Complexity: O(n) due to single traversation and subsequent O(n/2) check.
Space Complexity: O(n) because we store all node values in an array.

C C++Java Python C#JavaScript

using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public bool IsPalindrome(ListNode head) {
        List<int> values = new List<int>();
        ListNode current = head;
        while (current != null) {
            values.Add(current.val);
            current = current.next;
        }
        int left = 0, right = values.Count - 1;
        while (left < right) {
            if (values[left] != values[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}