Palindrome Linked List

password

URL

type

status

date

slug

summary

category

icon

Palindrome Linked List - LeetCode

Can you solve this real interview question? Palindrome Linked List - Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Example 1: [https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg] Input: head = [1,2,2,1] Output: true Example 2: [https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg] Input: head = [1,2] Output: false Constraints: * The number of nodes in the list is in the range [1, 105]. * 0 <= Node.val <= 9 Follow up: Could you do it in O(n) time and O(1) space?

https://leetcode.com/problems/palindrome-linked-list

Using Stack to solve is easy.

Approach Recursive

And the problem use Stack can also use recursive to solve.

Think about,

Use self.cur to store the first node in the list, when the function check traverses to the end of the list, we can comparison the node on the head of the list by self.cur with the node on the tail (current node in current check)

Then we back from recursion, move self.cur to next node, and return comparison result to previous recursive call, in this turn the tail is the node previous of the tail in last turn.