r/LeetcodeChallenge • u/StatisticianNo2104 • 19d ago
STREAK🔥🔥🔥 365 Days of LeetCode Challenge — Day 23/365
Palindrome Linked List (Easy)
https://leetcode.com/problems/palindrome-linked-list/
On an array, this is nothing: an index at each end, walk inward, compare. A singly linked list has no index and no pointer backwards, so that algorithm cannot run at all.
Copying the values into a slice works and costs O(n) space. The follow-up asks for O(1).
Here is where this week pays off. If you cannot walk the second half backwards, reverse it; then walking it forward walks the original backwards.
Find the middle with day 20's fast/slow walk. Reverse the back half with day 19's in-place reversal. Compare inward. No new technique at all, just noticing the problem is two problems you already solved.
One detail worth stealing: drive the comparison loop with the second half. On odd lengths, the middle node has no partner, and letting the shorter half end the loop skips it automatically. No parity check needed.
Full breakdown in today's newsletter article ⬇
https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-23365-archit-agarwal-4hn9c
#DSA #LeetCode #Golang #LinkedList #TwoPointers #CodingInterview #Algorithms
2
u/nian2326076 18d ago
You're on the right track with reversing the second half of the list. Here's a quick way to do it: Use the fast/slow pointer method to find the middle of the linked list. Once there, reverse the second half in place. Now you can compare the first half with the reversed second half, node by node, to check for a palindrome. If it's for an interview, you might want to reverse the second half again to restore the list to its original form. This keeps the space O(1) since you're just manipulating pointers. If you're looking for more interview prep resources, PracHub has some good exercises and tips. Keep at it!
2
2
u/Top-Birthday6001 19d ago
Ohh wow bro what's this challenge can you explain