AlgoViz
HomeLinked List

Check if LL is palindrome or not

Medium

Reverse the second half and compare

Problem

Given the head of a singly linked list representing a positive integer number. Each node of the linked list represents a digit of the number, with the 1st node containing the leftmost digit of the number and so on. Check whether the linked list values form a palindrome or not. Return true if it forms a palindrome, otherwise, return false. A palindrome is a sequence that reads the same forward and backwards.

In simple words

Find the middle, reverse the second half, then compare it against the first half node by node.

The idea

Find the middle with slow and fast pointers, reverse the half after it, then walk the two halves in step comparing values. That gives O(1) space where copying into an array would be O(n).

The trick

  • Compare only until the reversed half runs out — odd lengths leave a spare middle node.
  • Restore the list by reversing back if the caller may still use it.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
7
5
7
3
0
1
2
3
4

Step 1 of 2. Here's the example — head -> 3 -> 7 -> 5 -> 7 -> 3 Values: 3, 7, 5, 7, 3.

1/2
Optimal
timeO(n)spaceO(1)
1slow=fast=head2while fast and fast.next: slow=slow.next; fast=fast.next.next3second = reverse(slow)4while second: if head.val != second.val: return false; head=head.next; second=second.next5return true

Input

array
[3, 7, 5, 7, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 2 -> 1
Output:
true
Explanation:
Reads the same both ways.

Example 2

Input:
list = 1 -> 2 -> 3
Output:
false
Explanation:
Backwards it's 3,2,1 → false.

Example 3

Input:
list = 7
Output:
true
Explanation:
Single node is a palindrome.

Constraints

  • 1 <= number of nodes in the Linked List <= 10^5
  • 0 <= ListNode.val <= 9
  • The number represented does not contain any leading zeroes.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.