Basically, the problem is:
- Given a list of chars, do the following until it has only 1 element:
- Starting from the beginning, remove each second node of the list, for example doing this to "abcdefghij" should return "acegi"
- Starting from the end of the list produced by step 1, remove each second node, so doing this to "acegi" should return "aei"
- Do these steps until the list has only 1 element
The final solution to this particular list should be "i".
My solution to this is :
public class listexercise {
public static DLL<Character> removeFront(DLL<Character> list){
DLLNode<Character> tmp = list.getFirst().succ;
while(tmp != null){
list.delete(tmp);
if(tmp.succ == null) {
tmp.pred.succ = null;
break;
}
tmp = tmp.succ.succ;
}
return list;
}
public static DLL<Character> removeEnd(DLL<Character> list){
DLLNode<Character> tmp = list.getLast().pred;
while(tmp != null){
list.delete(tmp);
if(tmp.pred == null) {
tmp.succ.pred = null;
break;
}
tmp = tmp.pred.pred;
}
return list;
}
public static DLL<Character> rec(DLL<Character> list, int n){
if(list.length() == 1)
return list;
else if(n%2 == 1)
return rec(removeFront(list), n++);
else if(n%2 == 0)
return rec(removeEnd(list), n++);
return list;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
DLL<Character> list = new DLL<Character>();
String input = s.nextLine();
char[] parts = input.toCharArray();
for(int i=0; i<parts.length; i++)
list.insertLast(parts[i]);
System.out.println(rec(list,1).toString());
}
}
This gives me NPE on the removeFront or removeEnd. However if I use specifically only one of them at a time, they work perfectly, but when I put them in a recursion, there's a problem.
Any ideas how to fix this??
