234. Palindrome Linked List
On This Page
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
A simple solution to this problem is to:
- traverse the linked list
- storing the value of each node in an array.
Then, we could compare the array with its reversed version.
If they match, the linked list is a palindrome. Otherwise, it is not.
This solution takes
O(n) time (where
n is the number of nodes in the list), as we need to traverse the list once.
However, it also takes
O(n) space, as we store the value of each node in an array.
To solve the problem in
O(n) time and
O(1) space, we can use the two-pointer technique to find the middle of the linked list. Then, we can reverse the second half of the list in-place. After that, we can compare the first half with the reversed second half. If they match, the list is a palindrome.
Reversing a linked list in-place involves changing the next pointers of the nodes to point to the previous node. This process can be done with a constant amount of space.
- Initialize two pointers: slow and fast at the head of the list.
- Move slow one step at a time and fast two steps at a time.
- When fast reaches the end of the list, slow will be at the middle.
- Reverse the second half of the list starting from slow.
- Compare the first half of the list with the reversed second half.
- If they match, return true.
- If they don’t, return false.
class Solution: def isPalindrome(self, head: ListNode) -> bool: slow = fast = head # find the mid node while fast and fast.next: slow = slow.next fast = fast.next.next # reverse the second half prev = None cur = slow while cur: # 1 [1 2 3 4] nxt = cur.next # 2 cur.next = prev # 1.next = None prev = cur # 1, at the end of loop will be 4 cur = nxt # 2 # compare the first and second half nodes while prev: if prev.val != head.val: return False prev = prev.next head = head.next return True
Debug of Reversing
Assuming we have a linked list as
[1,2,3,4,5,6] and slow initially points to
4. Result should be
- Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
- cur points to 4
- prev = None
- First iteration:
- nxt is assigned 5 (the next node after cur)
- cur.next (the next node after 4) is assigned None
- prev is assigned 4
- cur is assigned 5 (nxt)
After first iteration:
- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 6
- cur points to 5
- prev points to 4
- Second iteration:
- nxt is assigned 6
- cur.next (the next node after 5) is assigned 4 (prev)
- prev is assigned 5
- cur is assigned 6 (nxt)
After second iteration:
- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 4, 6
- cur points to 6
- prev points to 5
- Third iteration:
- nxt is assigned None
- cur.next (the next node after 6) is assigned 5 (prev)
- prev is assigned 6
- cur is assigned None (nxt)
After third iteration:
- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 4, 6 -> 5
- cur points to None
- prev points to 6
None, we exit the while loop.
prev is pointing to the
head of the reversed second half of the list.
The list now looks like this:
1 -> 2 -> 3 -> 4 -> None and 6 -> 5 -> 4 -> None.