Workspace

Problem workspace

3 day streakD

Palindrome Linked List

EasyLinked ListsReversal

The challenge

Decide whether a list reads the same forward and backward while restoring its original structure.

The input is acyclic. Empty and single-node lists count as palindromes.

Example

[1, 2, 2, 1] → true; [1, 2, 3] → false.

Use the walkthrough below to inspect the input and each state change.

See Palindrome, step by step

Follow the pointers. Watch each link change.

4 nodes · singly linkedIDs = node identity · ∅ = null
Even palindrome: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head1A12A22A31A4∅
CurrentResultYellow arrow: changed next link
headA1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A11A2
A22A3
A32A4
A41null
Step 01 / 18

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 1 (A1) → 2 (A2) → 2 (A3) → 1 (A4); parameters: {}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

Only the second half needs reversing; comparing corresponding nodes is then a forward walk.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev


def is_palindrome(head):
    if head is None or head.next is None:
        return True
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow.next)
    a, b = head, second
    matches = True
    while b:
        if a.val != b.val:
            matches = False
        a, b = a.next, b.next
    slow.next = reverse(second)
    return matches

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap