Linked list reordering

Computer science is full of real-life examples. One such example is the linked list. A linked list is a data structure that has nodes attached. Now one may ask what is the difference between a linked list and an array. The difference lies in space consumption. A linked list is a noncontiguous data structure hence it ensures more optimized usage of space than an array. Similar to how an array consists of elements a linked list consists of nodes. Each node is divided into two parts

1. Data part
2. Pointer part

The data part in a linked list stores the value being held in the node while the pointer part holds the pointer to the next node so that the non-contiguous property of the linked list is ensured.

Now that we have seen the basic definition of a linked list let’s dive into its practical applications.

Practical applications

1. Image viewer: The previous and next images are linked and hence can easily be accessed by pressing the next and previous buttons.
2. Previous and next page in the browser: The same property is used in the previous and next buttons we see on top of the browser.
3. Music player: The next song and previous song is also accessed using this property.
4. The linked list is also an important data structure as it’s used in more complex concepts like graphs in the form of adjacency lists. It hence becomes important that this topic is covered before covering graphs.

Now that we have seen the practical concepts let’s get an all-round view of linked lists with the help of a LeetCode problem(medium difficulty).

Problem statement

Reorder List - LeetCode

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to L0→Ln→L1→Ln-1→L2→Ln-2→…

That is the first node has now the last node as its next node. The last node hs the next node as the initial second node which in turn has the second last node as its next node. This is the pattern followed until all the nodes are covered.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

We are expected to solve the problem in O(n) time complexity.

Approach

We can think of a two-pointer approach over here where one pointer points to the last node of the linked list and another pointer point to the first node of the linked list. We can say the node pointing to the first node as the left pointer and the pointer pointing to the last node as the right node. We store the address of the next node of the left node in a temp pointer and change the next element of the left pointer to the right pointer. The next right pointer is now made as to the temp pointer and the left pointer is advanced to become the temp pointer as told in the question.

The above steps have to be now repeated with the second node and the second last node. After the steps followed in the previous para the left pointer is now at the second node but what about the right pointer. The right pointer is still at the last element. It cannot come back to its previous node as in the linked list we can traverse only from head to tail, not from tail to head. This is where recursion saves us.

We advance the right node initially pointing to the head to the last node with the help of recursion. By doing this we store the elements of the linked list in a recursion stack. After the base case is encountered the function starts to wipe out its elements from the stack one by one hence traversing the linked list in reverse. Also, make sure that the left pointer is global, else the left pointer might not get updated in different function calls. Each time the left and right pointers change their values we must perform the same steps as I told in the first paragraph of this section.

One more thing we have to keep under check is the number of times we should follow the instruction to change the next pointers of the node. If this is continuously done until the write pointer reaches the first node it will lead to a wrong answer (Please dry run by taking examples). So this has to be done only till when the write pointer reaches the middle node.

Keeping these points in our mind we can now proceed to the coding part.

Code

Analysis

We can see that the entire list is traversed only once while recursion was in action. This makes the time complexity of the algorithm O(n) and even though we haven’t utilized any other data structure we have used recursion which in turn uses recursion stack. Therefore the space complexity becomes O(n).

With this, I hope you have understood the concept of linked lists and how recursion can be used along with linked lists. Please give a clap if you liked the article.