Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists 'a' and 'b'. The sublists should be made from alternating elements in the original list. So if the original list is 0->1->0->1->0->1 then one sublist should be 0->0->0 and the other should be 1->1->1.
This code is attributed to geeksforgeeks. I'm looking for code-review, optimizations and best practices. Specifically, please let me know if the way I have used a private constructor in code is acceptable within coding standards, and if not, an alternative.
Why I don't extend or reuse: I am prepping for interviews, and interviewers explicitly want you to code, in my experience. I request the reviewer to not insist on reusing, as I am aware in real life reusability is the right approach. This does not work in interviews.
Why don't I use a
Util
class instead nesting method inside linked list? That is because I need theNode
to be an internal data structure. Had I made aUtil
class, it would have no access to internal data structure and perform operations on the node's pointers.
final class AlternateSplitData<T> {
private final AlternateSplit<T> evenLL;
private final AlternateSplit<T> oddLL;
public AlternateSplitData(AlternateSplit<T> evenLL, AlternateSplit<T> oddLL) {
this.evenLL = evenLL;
this.oddLL = oddLL;
}
public AlternateSplit<T> getEvenLL() {
return evenLL;
}
public AlternateSplit<T> getOddLL() {
return oddLL;
}
}
public class AlternateSplit<T> {
private Node<T> first; // is private constructor the right thing to do ?
private AlternateSplit(Node<T> first) {
this.first = first;
}
public AlternateSplit(List<T> items) {
add(items);
}
private void add(List<T> items) {
Node<T> prev = null;
for (T item : items) {
Node<T> node = new Node<>(item);
if (first == null) {
first = prev = node;
} else {
prev.next = node;
prev = node;
}
}
}
private static class Node<T> {
private Node<T> next;
private T item;
Node(T item) {
this.item = item;
}
}
public AlternateSplitData<T> alternate() {
Node<T> temp = first;
Node<T> oddhead = null;
Node<T> odd = null;
Node<T> evenhead = null;
Node<T> even = null;
int count = 0;
while (temp != null) {
if (count % 2 == 0) {
if (evenhead == null) {
evenhead = temp;
even = temp;
} else {
even.next = temp;
even = temp;
}
} else {
if (oddhead == null) {
oddhead = temp;
odd = temp;
} else {
odd.next = temp;
odd = temp;
}
}
count++;
temp = temp.next;
}
if (even != null) {
even.next = null;
}
if (odd != null) {
odd.next = null;
}
return new AlternateSplitData<T>(new AlternateSplit<T>(evenhead), new AlternateSplit<T>(oddhead));
}
// size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
public List<T> toList() {
final List<T> list = new ArrayList<>();
if (first == null) return list;
for (Node<T> x = first; x != null; x = x.next) {
list.add(x.item);
}
return list;
}
@Override
public int hashCode() {
int hashCode = 1;
for (Node<T> x = first; x != null; x = x.next)
hashCode = 31*hashCode + (x.item == null ? 0 : x.item.hashCode());
return hashCode;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
AlternateSplit<T> other = (AlternateSplit<T>) obj;
Node<T> currentListNode = first;
Node<T> otherListNode = other.first;
while (currentListNode != null && otherListNode != null) {
if (currentListNode.item != otherListNode.item) return false;
currentListNode = currentListNode.next;
otherListNode = otherListNode.next;
}
return currentListNode == null && otherListNode == null;
}
}
public class AlternateSplitTest {
@Test
public void testEvenLength() {
AlternateSplit<Integer> as1 = new AlternateSplit<>(Arrays.asList(0, 1, 2, 3, 4, 5));
AlternateSplitData<Integer> list1 = as1.alternate();
assertEquals(new AlternateSplit<Integer>(Arrays.asList(0, 2, 4)), list1.getEvenLL());
assertEquals(new AlternateSplit<Integer>(Arrays.asList(1, 3, 5)), list1.getOddLL());
}
@Test
public void testOddLength() {
AlternateSplit<Integer> as2 = new AlternateSplit<>(Arrays.asList(0, 1, 2, 3, 4));
AlternateSplitData<Integer> list2 = as2.alternate();
assertEquals(new AlternateSplit<Integer>(Arrays.asList(0, 2, 4)), list2.getEvenLL());
assertEquals(new AlternateSplit<Integer>(Arrays.asList(1, 3)), list2.getOddLL());
}
@Test
public void testSingleElement() {
AlternateSplit<Integer> as3 = new AlternateSplit<>(Arrays.asList(0));
AlternateSplitData<Integer> list3 = as3.alternate();
assertEquals(new AlternateSplit<Integer>(Arrays.asList(0)), list3.getEvenLL());
assertEquals(new AlternateSplit<Integer>(Collections.EMPTY_LIST), list3.getOddLL());
}
}