How do you approach Palindrome Linked List?

Compare the sequence with its reverse - or better, compare from both ends toward the middle.

What is the time complexity of Palindrome Linked List?

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

What are common mistakes on Palindrome Linked List?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Palindrome Linked List

EasyData Structures

Description

Given the head of a singly linked list, return true if it is a palindrome (reads the same forward and backward) or false otherwise.

Note: For this problem, linked lists are represented as arrays for simplicity. The function takes the list as an array and returns a boolean.

Example 1

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

Output: true

Example 2

Input: head = [1,2]

Output: false

Example 3

Input: head = [1]

Output: true

Constraints

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

Palindrome Linked List: approach, complexity and pitfalls

An easy linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Compare the sequence with its reverse - or better, compare from both ends toward the middle.
Two pointers starting at the ends and moving inward detect any mismatch in one pass.
On a real linked list (no random access) the O(1)-space trick is: find the middle with fast/slow pointers, reverse the second half in place, then walk both halves together.

The optimal approach

Show the approach: Two Pointers from Both Ends

Compare the first and last values, move both pointers inward, and stop at the first mismatch. An empty or single-node list is trivially a palindrome.

On a pointer-based linked list where you cannot index from the back, the classic O(1)-space approach is: locate the middle with fast/slow pointers, reverse the second half in place, then compare the two halves node by node.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.

← Back to problems

Palindrome Linked List

EasyData Structures

Description

Given the head of a singly linked list, return true if it is a palindrome (reads the same forward and backward) or false otherwise.

Note: For this problem, linked lists are represented as arrays for simplicity. The function takes the list as an array and returns a boolean.

Example 1

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

Output: true

Example 2

Input: head = [1,2]

Output: false

Example 3

Input: head = [1]

Output: true

Constraints

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

Palindrome Linked List: approach, complexity and pitfalls

An easy linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Compare the sequence with its reverse - or better, compare from both ends toward the middle.
Two pointers starting at the ends and moving inward detect any mismatch in one pass.
On a real linked list (no random access) the O(1)-space trick is: find the middle with fast/slow pointers, reverse the second half in place, then walk both halves together.

The optimal approach

Show the approach: Two Pointers from Both Ends

Compare the first and last values, move both pointers inward, and stop at the first mismatch. An empty or single-node list is trivially a palindrome.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.