merge sort algorithm<\/strong>, but the only problem is that here we are not utilizing the information given to us in the problem that the linked list is already sorted in alternating ascending and descending orders.<\/p>\nIf we are using merge sort to sort the linked list the time complexity will be O(NlogN), so now we will try to think can we utilize the information given to us in the problem and will try to solve the problem in lower time complexity.<\/p>\n
Before jumping to the approach, try to think how you can approach this problem. If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.<\/p>\n
Let\u2019s move on to the approach section.<\/p>\n
Approach<\/h3>\n
We have to divide the problem into three steps: <\/p>\n
\n- The first step is to split the linked list into two linked lists. One list is for nodes in ascending order and the second is for nodes in descending order. <\/li>\n
- After this step, We have to reverse the second linked list to change its order from descending to ascending. <\/li>\n
- After this step our both linked lists are sorted in ascending order, Now merge both lists into a single list in such fashion that the final list will also remain sorted.<\/li>\n<\/ul>\n
Algorithm<\/h3>\n\n- We have to divide this problem into three steps.<\/li>\n
- The first step is to split the linked list into two lists.<\/li>\n
- Initialize two pointer variables of the type node.<\/li>\n
- One pointer for nodes of ascending order and another is for nodes in descending order.<\/li>\n
- Now we will have two lists, one is sorted in ascending order and another list is sorted in descending order.<\/li>\n
- Now reverse the second list. This will make the second linked list sorted in ascending order.<\/li>\n
- Now we have two sorted linked lists.<\/li>\n
- Merge both the linked list.<\/li>\n
- The final linked list after merging both the linked lists will be our resultant linked list.<\/li>\n<\/ul>\n
Code Implementation<\/h3>\n\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926345566-114.Sort%20a%20linked%20list%20that%20is%20sorted%20alternating%20ascending%20and%20descending%20orders_Artboard%203.png\")
<\/p>\n