I am currently tasked with creating a recursive method to determine the length of a circular doubly linked list, that being a doubly linked list where the final node points back to the head node and vice versa.
I can’t check for equality to null because due to the circular nature of the list, but the only argument I can supply is a head node, which I can’t check equality to as it changes as I recurse.
My code stands as follows:
public int size(ListNode head) {
if(head.element == null || head == null) return 0;
head.element = null;
return 1 + size(head.next);
}
I’ve attempted to look at the element at the pointer, setting it to null then moving on such that when the method wraps around to the original head pointer, it detects the null and stops recursing. However, this does not work at all.
1
I am assuming that by “this does not work at all” you mean that you run into problems down the line because you set every element to null.
If you cannot carry information on a node and you cannot change the method parameters I don’t think it is possible to solve this. Therefore I would add a new internal method to do the actual recursive counting:
public int size(ListNode head) {
if(head == null) return 0;
return 1 + recursiveSize(head.next, head);
}
private int recursiveSize(ListNode current, ListNode start) {
if(current == start) return 0;
return 1 + recursiveSize(current.next, start)
}
2