So let’s break down the approach. We are using a singly linked list, and are not given the size of the Linked List. The only fields are the value, and the next node. The starting code provided by the question is below:
I’ll use this basic approach:
Get the half-way point of the list.
Reverse the second half of the list.
Compare the two halves.
I can reverse the list by using two pointers, one of which will move 2 nodes at a time, while the other moves 1. If we check when the faster ptr reaches the end, then the slower ptr will be at the half.
Step one is done, now time to reverse the second half of the list. This is a singly linked list, so we will need to use three pointers to achieve this.
prev will point to the previous node. curr will point to the current node. nextBuffer will point to the next node.
We will store the next node in nextBuffer.
Because we are reversing, we will then set the next value in curr to the value of prev, which will initially be null.
We will then set prev to curr, when we increment curr, then prev will accurately represent the previous node.
Finally, we increment curr by setting it the value of the nextBuffer which we set in step 1.
Step two done! Now it’s just a matter of comparing the two halves. The head pointer represents the first half of the list, while the prev pointer contains the second, reversed, half of the list.
The final (submitted) solution is below:
All the test cases passed, but only beating 34.92% of other Java submissions isn’t anything to brag about…. 2ms is quite slow.
The alternatives to my solution are a stack-based solution, and a recursive solution. All of these have O(n) time complexity, but could very well be much quicker.