Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
The description was taken from https://leetcode.com/problems/palindrome-linked-list/.
#O(N) Time, O(1) Space
class Solution:
def isPalindrome(self, head):
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
previous, current = None, slow
while current:
bridge = current.next
current.next = previous
previous = current
current = bridge
current = previous
while current is not None:
if current.val != head.val:
return False
current = current.next
head = head.next
return TrueThis problem can be solved with the combined solutions from Middle of the Linked List and Reverse Linked List.
We can use a slow and fast pointer to get the middle element and from there, we will reverse the node pointers from the middle element to the end of the list.
That will allow us to break the linked list at the middle and have two pointers to make the old tail be the new head of a separate sublist. We can compare the values of the nodes at these two pointers and if they match, we will move them inward to compare the next two. If there is no mismatch in values, the linked list is a palindrome.
Let's start off by initializing our fast and slow pointers at the head of the linked list.
fast = slow = head
Then, we will traverse the list with our pointers. During each iteration, we will increment the slow pointer once and the fast pointer twice.
Once the fast pointer is at the end of the list, the slow pointer will be halfway to the end.
while fast and fast.next: fast = fast.next.next slow = slow.next
Once the slow pointer is at the midpoint, we will begin reversing the second half of the list.
We will do this by utilizing three pointers. Our previous pointer will be used to track the previous node, current will be used to track the current node, and bridge will be used to track the next node.
We will initialize our previous and current pointers, with the current pointer being where slow was. The node the slow pointer is at will be the head of its sublist once reversed.
previous, current = None, slow
While the current pointer isn't at a null node, we continue moving down the list, setting each current pointer's next reference to the previous node.
while current:
At the beginning of each iteration, we will save bridge as the next node.
bridge = current.next
We want to do this because once we overwrite current.next and set it to the previous node, we will lose our bridge to get to the next node.
Once we saved our bridge, we will overwrite the reference to our next node by setting it to the previous node, previous.
current.next = previous
We will then move our previous pointer to the current pointer, and our current pointer will cross the bridge to the next node.
previous = current
current = bridge
Once we have broke from the loop, that means that the current is now at the null node, so we'll set it back a node to its previous value.
current = previous
Once we have reversed the node pointers, our list will basically go from this:
head1->2->3->3->2->1None
to this:
head1->2->3->None<-3<-2<-1current
While current has not reached the None value, we will keep moving it and the head pointer to their next places.
If there is a mismatch in values, we will return false.
while current is not None:
if current.val != head.val:
return False
current = current.next
head = head.next
Otherwise, if we break from the loop then all of the values match up and we will return true.
return True