Alternating split of a given singly linked list

Question

Write a function AlternatingSplit() that takes one list and divides its nodes to make two smaller lists a and b. 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 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.

1. 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.

2. Why don't I use a Util class instead nesting method inside linked list? That is because I need the Node to be an internal data structure. If I made a Util 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());
 
 }
 
}

Answer 1

Having a list whose type is AlternateSplitData<T> makes it totally impractical to use. It's a singly linked list. I don't care that it came from an alternating splitting process. I just want it to interoperate with any other code that works with linked lists.

alternate() seems to contain a lot of code for my taste. In particular,

if (even != null) {
 even.next = null;
}
if (odd != null) {
 odd.next = null;
}

is totally superfluous.

I suggest naming variables like oddTail for clarity, and to adhere to Java capitalization conventions.

public AlternateSplitData<T> alternate() {
 Node<T> oddHead = null, oddTail,
 evenHead = null, evenTail;
 if (first != null) {
 evenHead = evenTail = temp;
 if (first.next != null) {
 oddHead = oddTail = temp;
 } 
 } 
 if (oddHead != null) {
 boolean isEven = false;
 for (Node<T> temp = oddHead.next; temp != null; temp = temp.next) {
 if ((isEven = !isEven)) {
 evenTail = (evenTail.next = temp);
 } else {
 oddTail = (oddTail.next = temp);
 }
 } 
 } 
 return new AlternateSplitData<T>(evenHead, oddHead);
}

• h.j.k.: if ((isEven = !isEven)) took me longer than usual to take it in. Seems like a nice trick after you fight the instinct that it 'looks wrong'. ;p

Answer 2

All interviewers are different. As an interviewer I wouldn't care about irrelevant details. I'd be very disappointed however by the implementation of alternate:

• oddhead and evenhead do not belong here. They are properties of the AlternateSplitData, and should be initialized by constructor. Similarly, AlternateSplitData should export methods to add item to one of their lists.

• count is totally bogus. Doing even, odd, even, odd... doesn't call for increments and modulos.

That said, I'd expect something along the lines of

public AlternateSplitData<T> alternate(Node<T> begin) {
 AlternateSplitData<T> asd = new AlternateSplitData<T>();
 while (begin) {
 asd.addEven(begin);
 if ((begin = begin.next) == null) break;
 asd.addOdd(begin);
 begin = begin.next;
 }
 return asd;
}

with addEven and addOdd methods dispatching add to an appropriate list.

Answer 3

I think @user50399 and @vnp have made some good suggestions already, so I will touch on two lighter issues...

1. The following comment is misleading:

   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);
   }
   

   Node<T> first is not a constructor, and you have one private and public constructors each. Better to remove.

2. Your tests, at first glance, seem to imply that alternate() is actually splitting the list up into lists containing even and odd numbers. This is because the method name simply said getEvenLL() and getOddLL(). Furthermore, I get it that your implementation is simply doing a modulus with 2, hence the concept of 'odd' and 'even', but a layperson will simply read your test data as "0 is the first element, 1 is the second, etc." This gets even more confusing, since now they will be concluding that getting the odd elements should be 0, 2, 4. Perhaps renaming the method as getOddIndexedLL() will be marginally better, and to use pseudo-random integers to minimize any confusion as to what the method is returning.