LeetCode - Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/
Problems
Given a singly linked list, check if this linked list is palin or not
Solution
Firstly, we may need to split the linked list into 2 parts: the left part and the right part. We can archive this by using fast and slow pointers (slow go 1 step and fast go 2 steps).
Assume we have 2 parts of the given linked list, i have two solutions to check the given linked list is palin or not.
The first solution
We store the first parts of linked list into a stack. Then we can traverse through the second part of linked list, for each node, we pop the stack by one and compare the value. If we can reach into the end of the stack, then the given linked list is palin.
This solution has O(N) memory and O(N) time complexity
The second solution
We will reverse the first part of linked list, then we compare the reversed linked list and the second part. If these two linked list are the same, then the given linked list is palin.
This solution has O(1) memory and O(N) time complexity
Conclusion
So, which solution is the best solution? I don’t know, it depends. The second solution seems better since it only has O(1) memory complexity but it will change the given input. The first solution will keep the given input stay the same.
Code for the second solution
1 | /** |
Support me via: https://ko-fi.com/iamquang95