Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same until end of the linked list.
Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8Output:
Linked List: 1->2->5->6
I'm looking for code review, optimizations and best practices.
public class DeleteNAfterM<T> {
private Node<T> first;
private Node<T> last;
private int size;
public DeleteNAfterM(List<T> list) {
for (T item : list) {
create(item);
}
}
private void create(T item) {
Node<T> node = new Node<T>(item);
Node<T> l = last;
if (first == null) {
first = node;
} else {
l.next = node;
}
last = node;
size++;
}
private static class Node<T> {
private T item;
private Node<T> next;
Node(T item) {
this.item = item;
}
}
public void deleteNAfterM(int m, int n) {
if (first == null) {
throw new IllegalArgumentException(" the linkedlist should not empty.");
}
if (m < 0) {
throw new IllegalArgumentException("m: " + m + " should not be less than zero.");
}
if (n < 0) {
throw new IllegalArgumentException("n: " + n + " should not be less than zero.");
}
if (m == 0 && n > 0) {
size = 0;
first = last = null;
return;
}
Node<T> node = first;
while (node != null) {
for (int i = 1; i < m && node != null; i++) {
node = node.next; // can be thought of as int x = a[i];
}
if (node == null || node.next == null) return;
Node<T> temp = node;
for (int i = 0; i < n && temp != null; i++) {
temp = temp.next; // can be thought of as int x = a[i];
size--;
}
if (temp == null) return;
node.next = temp.next;
node = node.next;
}
}
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<T> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
}
public class DeleteNAfterMTest {
@Test
public void test1() {
// last node is not deleted
DeleteNAfterM<Integer> deleteMAfterN1 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
deleteMAfterN1.deleteNAfterM(2, 2);
Object[] itemList1 = deleteMAfterN1.toArray();
Integer[] expected1 = {1, 2, 5, 6};
assertTrue(Arrays.equals(expected1, Arrays.asList(itemList1).toArray(new Integer[itemList1.length])));
}
@Test
public void test2() {
// last node is deleted
DeleteNAfterM<Integer> deleteMAfterN2 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
deleteMAfterN2.deleteNAfterM(2, 1);
Object[] itemList2 = deleteMAfterN2.toArray();
Integer[] expected2 = {1, 2, 4, 5};
assertTrue(Arrays.equals(expected2, Arrays.asList(itemList2).toArray(new Integer[itemList2.length])));
}
@Test
public void test3() {
// edge case - nothing should be deleted
DeleteNAfterM<Integer> deleteMAfterN3 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
deleteMAfterN3.deleteNAfterM(4, 0);
Object[] itemList3 = deleteMAfterN3.toArray();
Integer[] expected3 = {1, 2, 3, 4, 5, 6};
assertTrue(Arrays.equals(expected3, Arrays.asList(itemList3).toArray(new Integer[itemList3.length])));
}
@Test
public void test4() {
// edge case - everything should be deleted.
DeleteNAfterM<Integer> deleteMAfterN4 = new DeleteNAfterM<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
deleteMAfterN4.deleteNAfterM(0, 1);
Object[] itemList4 = deleteMAfterN4.toArray();
Integer[] expected4 = {};
assertTrue(Arrays.equals(expected4, Arrays.asList(itemList4).toArray(new Integer[itemList4.length])));
}
}