Write a function
AlternatingSplit()
that takes one list and divides its nodes to make two smaller listsa
andb
. The sublists should be made from alternating elements in the original list.Example: if the original list is
0->1->0->1->0->1
, then one sublist should be0->0->0
and the other should be1->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. If 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());
}
}