A node has a next and down pointer. Merge the linked-list such that end result is sorted. Here we have a top level linked-list, followed by a down-list.
If { 10 : {20, 30} , 35 { 40, 50 } } is the input data structure, it means that 10 is connected to 35, using the next pointer. 10 is connected to 20 and 20 to 30 using the down pointer, and 35 is connected to 40 and 40 to 50 using the down pointer.
Only the top level list {10 -> 35} use the next pointer, the down level links {10 -> 20 -> 30} and {35 -> 40 -> 50} use the down pointer ONLY.
The output should be a list 10 - 20 - 30 - 35 - 40 - 50, and down ptr should be null for all.
This question, like many of my previous questions, is attributed to GeeksForGeeks. This code was previously solved here.
Looking for code-review, best practices and optimizations. Verifying complexity to be \$O(mn * logn)\$, where \$n\$ is the length of number of nodes linked by next ptr, while \$m\$ is the max length of the linked list through the down ptr.
public class FlattenLinkedList {
private Node first;
private Node last;
private final PriorityQueue<Node> queue;
private int size;
public FlattenLinkedList(List<Integer> nodes) {
queue = new PriorityQueue<Node>(11, new FlattenListComparator());
for (Integer item : nodes) {
add(item);
}
}
/**
*
* 10 -(next)-> 20 -(next)-> 30
* | | |
* down down down
* | | |
* 12 25 35
* | | |
* 100 400 200
*
* To represent such a list in the map,
* keys of such a map would be 10, 20 and 30.
* The values of such a map would be
* key: 10, values: a list of 12, 100
* key: 20, values: a list of 25, 400
* key: 30, values: a list of 35, 200
*
*/
public FlattenLinkedList(LinkedHashMap<Integer, List<Integer>> nodes) {
queue = new PriorityQueue<>(11, new FlattenListComparator());
for (Integer item : nodes.keySet()) {
add(item);
}
Node head = first;
for (List<Integer> items : nodes.values()) {
addDown(head, items);
head = head.next;
}
}
private void add(int item) {
final Node node = new Node(item);
queue.add(node);
if (first == null) {
first = last = node;
} else {
last.next = node;
last = node;
}
size++;
}
private void addDown(Node head, List<Integer> list) {
Node prev = null;
for (Integer item : list) {
Node node = new Node(item);
if (prev == null) {
prev = node;
head.down = node;
} else {
prev.down = node;
}
prev = node;
}
size = size + list.size();
}
private static class FlattenListComparator implements Comparator<Node> {
@Override
public int compare(Node node1, Node node2) {
return node1.item - node2.item;
}
}
private static class Node {
private Node next;
private Node down;
private int item;
Node(int item) {
this.item = item;
}
}
public void flatten() {
Node prev = null;
while (!queue.isEmpty()) {
Node currNode = queue.poll();
if (prev == null) {
prev = first = currNode;
} else {
prev.next = currNode;
prev = currNode;
}
if (currNode.down != null) {
queue.add(currNode.down);
}
}
}
public int[] toArray() {
int[] arr = new int[size];
int count = 0;
for (Node x = first; x != null; x = x.next) {
arr[count++] = x.item;
}
return arr;
}
}
public class FlattenLinkedListTest {
@Test
public void test1() {
LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
map.put(10, Arrays.asList(20, 30));
map.put(40, new ArrayList<Integer>());
map.put(70, Arrays.asList(80, 90));
map.put(100, Arrays.asList(110, 120));
FlattenLinkedList flat = new FlattenLinkedList(map);
flat.flatten();
int[] arr = {10, 20, 30, 40, 70, 80, 90, 100, 110, 120};
assertArrayEquals(arr, flat.toArray());
}
@Test
public void test2() {
LinkedHashMap<Integer, List<Integer>> map1 = new LinkedHashMap<Integer, List<Integer>>();
map1.put(1, Arrays.asList(80, 90));
map1.put(2, Arrays.asList(70, 75));
map1.put(3, Arrays.asList(60, 65));
map1.put(4, Arrays.asList(50, 55));
map1.put(5, Arrays.asList(40, 45));
FlattenLinkedList flat1 = new FlattenLinkedList(map1);
flat1.flatten();
int[] arr1 = {1, 2, 3, 4, 5, 40, 45, 50, 55, 60, 65, 70, 75, 80, 90};
assertArrayEquals(arr1, flat1.toArray());
}
}
