Given three linked lists, say a, b and c, find one node from each list such that the sum of the values of the nodes is equal to a given number. For example, if the three linked lists are 12->6->29, 23->5->8 and 90->20->59, and the given number is 101, the output should be tripel “6 5 90″.
This question is attributed to geeksforgeeks.
Looking for code review, optimizations, best practices. Please ignore reviews which include improvements to class / variable names. They are named so for personal reasons and well aware they need to be better.
class NodeLL {
NodeLL next;
int item;
NodeLL(int item) {
this.item = item;
}
}
class LList {
private NodeLL first;
private NodeLL last;
public LList(List<Integer> list) {
for (int i : list) {
add(i);
}
}
private void add(int i) {
NodeLL node = new NodeLL(i);
if (first == null) {
first = last = node;
} else {
last.next = node;
last = node;
}
}
public void setFirst(NodeLL first) {
this.first = first;
}
public NodeLL getFirst() {
return first;
}
public void setLast(NodeLL last) {
this.last = last;
}
public NodeLL getLast() {
return last;
}
public List<Integer> toList() {
final List<Integer> list = new ArrayList<>();
for (NodeLL x = first; x != null; x = x.next) {
list.add(x.item);
}
return list;
}
}
public final class TripletLL {
private TripletLL() { }
// this util function can be utilized independently, not just to find triple LL, thus kept it public
public static void sort(LList linkedList) {
NodeLL first = sort (linkedList.getFirst(), linkedList.getLast());
linkedList.setFirst(first);
}
// this util function can be utilized independently, not just to find triple LL, thus kept it public
public static NodeLL midPoint(NodeLL node) {
NodeLL fast = node.next;
NodeLL slow = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private static NodeLL sort (NodeLL nodeStart, NodeLL nodeEnd) {
if (nodeStart == nodeEnd) return nodeStart;
NodeLL midpoint = midPoint (nodeStart);
NodeLL tempMidpoint = midpoint.next;
midpoint.next = null;
NodeLL n1 = sort (nodeStart, midpoint);
NodeLL n2 = sort (tempMidpoint, nodeEnd);
return merge(n1, n2);
}
private static NodeLL merge (NodeLL node1, NodeLL node2) {
assert node1 != null && node2 != null;
NodeLL head = null;
NodeLL prev = null;
NodeLL aux = null;
while (node1 != null && node2 != null) {
if (node1.item < node2.item) {
aux = node1;
node1 = node1.next;
} else {
aux = node2;
node2= node2.next;
}
if (prev == null) {
head = prev = aux;
} else {
prev.next = aux;
prev = aux;
}
}
prev.next = node1 == null ? node2 : node1;
return head;
}
private static void reverse(LList ll) {
NodeLL prev = null;
NodeLL curr = ll.getFirst();
NodeLL next = ll.getFirst();
while (curr != null) {
next = next.next;
curr.next = prev;
prev = curr;
curr = next;
}
ll.setFirst(prev);
}
/**
* Linkedlist structure changes, original structure is not maintained.
*
* @param ll1 the first linkedlist.
* @param ll2 the second linkedlist
* @param ll3 the third linkedlist
* @param value the value, which individual nodes from a linkedlist should sum upto.
* @return the 3 values/items each belonging to different linkedlist, which sum to the value.
*/
public static List<Integer> returnThree(LList ll1, LList ll2, LList ll3, int value) {
final List<Integer> list = new ArrayList<Integer>();
NodeLL node1 = ll1.getFirst(); // node belonging to first linkedlist
sort(ll2);
sort(ll3);
reverse(ll3);
NodeLL node2First = ll2.getFirst();
NodeLL node3First = ll3.getFirst();
NodeLL node2 = node2First; // node belonging to second linkedlist
NodeLL node3 = node3First; // node belonging to second linkedlist
boolean found = false;
while (node1 != null) {
while (node2 != null && node3 != null) {
int sum = node1.item + node2.item + node3.item;
if (sum == value) {
list.add(node1.item);
list.add(node2.item);
list.add(node3.item);
found = true;
break;
} else {
if (sum < value) {
node2 = node2.next;
} else {
node3 = node3.next;
}
}
}
if (found) {
break;
}
// resetting nodes to first.
node2 = node2First;
node3 = node3First;
node1 = node1.next;
}
return list;
}
}
public class TripletLLTest {
@Test
public void test1() {
LList ll1 = new LList(Arrays.asList(12, 6, 29));
LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
LList ll3 = new LList(Arrays.asList(90, 20, 59));
assertEquals(Arrays.asList(6, 5, 90), TripletLL.returnThree(ll1, ll2, ll3, 101));
}
@Test
public void test2() {
LList ll1 = new LList(Arrays.asList(12, 6, 29));
LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
LList ll3 = new LList(Arrays.asList(90, 20, 59));
assertEquals(Arrays.asList(12, 5, 90), TripletLL.returnThree(ll1, ll2, ll3, 107));
}
@Test
public void test3() {
LList ll1 = new LList(Arrays.asList(12, 6, 29));
LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
LList ll3 = new LList(Arrays.asList(90, 20, 59));
assertEquals(Arrays.asList(6, 23, 20), TripletLL.returnThree(ll1, ll2, ll3, 49));
}
@Test
public void test4() {
LList ll1 = new LList(Arrays.asList(12, 6, 29));
LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
LList ll3 = new LList(Arrays.asList(90, 20, 59));
assertEquals(Collections.EMPTY_LIST, TripletLL.returnThree(ll1, ll2, ll3, 50));
}
}
