Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Palindrome Linked List

Palindrome Linked List

Master this topic with zero to advance depth.

Palindrome Linked List

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

Visual Representation

List: 1 -> 2 -> 2 -> 1 1. Find mid: 2 (first 2) 2. Reverse second half: 1 -> 2 3. Compare halves: (1,2) == (1,2) -> true
Easy

Examples

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

Level I: Brute Force (Array Copy)

Intuition

Copy the values of the linked list into an array and then check if the array is a palindrome using two pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->2->1. Array: [1,2,2,1]. i=0, j=3: 1==1. i=1, j=2: 2==2. Match!

java
public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    while (head != null) { vals.add(head.val); head = head.next; }
    int i = 0, j = vals.size() - 1;
    while (i < j) { if (!vals.get(i).equals(vals.get(j))) return false; i++; j--; }
    return true;
}

⚠️ Common Pitfalls & Tips

O(N) space is required.

Visual Trace (Array)

List: 1 -> 2 -> 3 -> 2 -> 1 Array: [1, 2, 3, 2, 1] i=0, j=4: 1==1 i=1, j=3: 2==2 Match!
Approach 2

Level II: Recursive / Stack-based

Intuition

Compare nodes from outside-in. A stack helps us access nodes in reverse order.

Visual Trace (Stack)

Stack: [1, 2, 2, 1] Compare Pop(1) with Head(1) -> Match
⏱ O(N)💾 O(N)
java
public boolean isPalindrome(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    ListNode curr = head;
    while (curr != null) { stack.push(curr.val); curr = curr.next; }
    curr = head;
    while (curr != null) { if (curr.val != stack.pop()) return false; curr = curr.next; }
    return true;
}
Approach 3

Level III: Optimal (Reverse Second Half)

Intuition

Find the middle of the linked list using fast/slow pointers. Reverse the second half of the list. Compare the two halves. Finally, restore the list (optional).

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->2->1.

  1. Mid: 2.
  2. Reverse second half: 1->2.
  3. Compare (1->2) and (1->2).
java
public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode prev = null, curr = slow;
    while (curr != null) { ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; }
    ListNode p1 = head, p2 = prev;
    while (p2 != null) { if (p1.val != p2.val) return false; p1 = p1.next; p2 = p2.next; }
    return true;
}

⚠️ Common Pitfalls & Tips

Be careful when the list length is odd; the slow pointer will be exactly at the middle node, and reversing from it works fine.

← Previous QuestionIntersection of Two Linked Lists
Next Question →Remove Duplicates from Sorted List