Problem 24.20 Pg.407 in EPI (Java) asks to reuse the doubly linked list for BST using previous and next fields for the left and right children respectively. However, in the solution it looks like the node references are not being updated, rather they are assigned new address. Is this a typo or am I missing something: (I have attached the code snippet from the book below and my fix to solve the problem with the given constraints).
Thanks!
In the book:
private static DoublyLinkedListNode < Integer > buildSortedListHelper(int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end-start) / 2;
// possible voilation of problem constraint below as this will assign a new address to the nodes rather than reusing them
DoublyLinkedListNode cur = new DoublyLinkedListNode<>(head.data, left, null);
head = head.next;
cur.next = buildSortedListHelper(mid+1, end);
return cur;
}
My fix to the code:
private static DoublyLinkedListNode < Integer > buildSortedListHelper(int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end-start) / 2;
// my fix to satisfy the constraint
DoublyLinkedListNode cur = head;
cur.left = left;
head = head.next;
cur.next = buildSortedListHelper(mid+1, end);
return cur;
}
For reference purposes:
private static DoublyLinkedListNode head;
public static DoublyLinkedListNode buildBSTFromSortedList(DoublyLinkedListNode L, int length){
head = L;
return buildSortedListHelper(0, length);
}