Daily Coding Problem-Sort a Linked List

This is a coding problem that was asked in Google.

Problem Statement:- Given a linked list, how can we sort it in O(nlogn) time complexity.

Input: 4 — > 1 — > -3 — > 11

Output: -3 — > 1 — > 4 — > 11

If space is not a problem, we can easily iterate over the linked list, copy it in another array and then run merge sort on it and voila we have O(nlogn) time complexity with O(n) space.

But let’s add one more constraint now. What if we want to achieve a sorted linked list but in O(logn) space in short sort the linked list in place.

Before we jump on the solution, let’s take a step back and think how can we achieve it. One thing that is clear about the solution is that, as we need to achieve O(nlogn) time complexity, we will be using merge sort for our purpose. And merge sort works on the concept of divide and conquer.

Let’s look at the diagram to understand better.

Similar to how we split array into two halfs, we are going to split our linked list into two halfs.

But the catch is in case of linked list how do we figure out what is the mid element. In order to figure that out, we are going to make use of two pointers, one slow and other fast.