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. Looking for code-review, best practices and optimizations.
Verifying complexity to be O(n), where n is the total nodes in the linked-list.
public class FlattenLinkedList {
private Node first;
private Node last;
public FlattenLinkedList(List<Integer> nodes) {
for (Integer item : nodes) {
add(item);
}
}
public FlattenLinkedList(LinkedHashMap<Integer, List<Integer>> nodes) {
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);
if (first == null) {
first = last = node;
} else {
last.next = node;
last = node;
}
}
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;
}
}
private static class Node {
private Node next;
private Node down;
private int item;
Node(int item) {
this.item = item;
}
}
public void flatten() {
Node currNode = first;
while (currNode != null) {
merge(currNode);
currNode = currNode.next;
}
}
private void merge(Node node) {
Node nodeHorizontal = first;
Node nodeVertical = node.down;
node.down = null;
if (nodeVertical == null) {
return;
}
Node prev = null;
while (nodeHorizontal != null && nodeVertical != null) {
if (nodeHorizontal.item < nodeVertical.item) {
if (prev == null) {
prev = nodeHorizontal;
} else {
prev.next = nodeHorizontal;
prev = prev.next;
}
nodeHorizontal = nodeHorizontal.next;
} else {
if (prev == null) {
prev = nodeVertical;
} else {
prev.next = nodeVertical;
prev = prev.next;
}
nodeVertical = nodeVertical.next;
}
}
prev.next = nodeHorizontal != null ? nodeHorizontal : nodeVertical;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((last == null) ? 0 : last.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FlattenLinkedList other = (FlattenLinkedList) obj;
Node thisNode = first;
Node otherNode = other.first;
while (thisNode != null && otherNode != null) {
if (thisNode.item != otherNode.item) return false;
thisNode = thisNode.next;
otherNode = otherNode.next;
}
return thisNode == null && otherNode == null;
}
}
public class FlattenLinkedListTest {
@Test
public void test() {
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 flat1 = new FlattenLinkedList(map);
flat1.flatten();
FlattenLinkedList flat2 = new FlattenLinkedList(new ArrayList<Integer>(Arrays.asList(10, 20, 30, 40, 70, 80, 90, 100, 110, 120)));
assertTrue(flat1.equals(flat2));
}
}