Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Build confidence with an intuition-first walkthrough focused on linked list fundamentals.
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:
[1, 105].0 <= Node.val <= 9O(n) time and O(1) space?Problem summary: Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List · Two Pointers · Stack
[1,2,2,1]
[1,2]
palindrome-number)valid-palindrome)reverse-linked-list)maximum-twin-sum-of-a-linked-list)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #234: Palindrome Linked List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
while (pre != null) {
if (pre.val != head.val) {
return false;
}
pre = pre.next;
head = head.next;
}
return true;
}
}
// Accepted solution for LeetCode #234: Palindrome Linked List
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
var pre *ListNode
cur := slow.Next
for cur != nil {
t := cur.Next
cur.Next = pre
pre = cur
cur = t
}
for pre != nil {
if pre.Val != head.Val {
return false
}
pre, head = pre.Next, head.Next
}
return true
}
# Accepted solution for LeetCode #234: Palindrome Linked List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
pre, cur = None, slow.next
while cur:
t = cur.next
cur.next = pre
pre, cur = cur, t
while pre:
if pre.val != head.val:
return False
pre, head = pre.next, head.next
return True
// Accepted solution for LeetCode #234: Palindrome Linked List
// #Easy #Top_100_Liked_Questions #Two_Pointers #Stack #Linked_List #Recursion
// #Level_2_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(n)_Space_O(1)
// #2024_09_11_Time_43_ms_(85.29%)_Space_9.2_MB_(34.31%)
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
let mut ref_node = &head;
let mut len = 0;
while let Some(ref node) = &ref_node {
ref_node = &node.next;
len += 1;
}
ref_node = &head;
let mut i = 0;
let mut num = 0;
let mut skip_num = if len % 2 == 1 { len / 2 + 1 } else { 0 };
while let Some(node) = ref_node {
ref_node = &node.next;
if skip_num > 0 && skip_num - 1 == i {
skip_num = 0;
continue;
}
if i < len / 2 {
num = num * 10 + node.val as usize;
} else {
num -= node.val as usize * 10_usize.pow(i - len / 2);
}
i += 1;
}
num == 0
}
}
// Accepted solution for LeetCode #234: Palindrome Linked List
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function isPalindrome(head: ListNode | null): boolean {
let slow: ListNode = head,
fast: ListNode = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
let cur: ListNode = slow.next;
slow.next = null;
let prev: ListNode = null;
while (cur != null) {
let t: ListNode = cur.next;
cur.next = prev;
prev = cur;
cur = t;
}
while (prev != null) {
if (prev.val != head.val) return false;
prev = prev.next;
head = head.next;
}
return true;
}
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.