Loading...
Loading...
Loading...
A college portal stores a student's internal marks as a singly linked list: each node holds one mark and a link to the next node. The admin wants the list sorted from the lowest mark to the highest.
Build the linked list from the input in the given order. Then sort it by changing the links between nodes, without copying the marks into an array or a collection. Print the marks of the sorted list from head to tail.
Example
Input
6 45 12 78 33 12 90
Output
12 12 33 45 78 90
The sorted list is 12 12 33 45 78 90. Both 12s stay in the list.
Try the problem first. Open one hint at a time.
A list of 0 or 1 nodes is already sorted. Otherwise, split the list into two halves, sort each half, then merge them.
Find the middle with two pointers: a slow one that moves one node and a fast one that moves two. Start fast at head.next so a 2-node list splits into 1 + 1.
Cut the list after the middle node by setting its next to null. Without the cut, the first half still holds the whole list.
Merge with a dummy node: keep attaching the smaller front node, and attach the rest of the longer list at the end.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor