A grammar question about c++

BinaryTree* sortedListToBST(开发者_运维技巧ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

This is a function transferring sorted list to BST.. I don't understand in 1st line. Why "ListNode *&"... if just "ListNode*" why wrong? thank you for any explanation.

Thanks. One more question.. if just "ListNode &list" it must be wrong, why we need "*" also,.. amateur of C++ forgive me my stupid question

This is a reference to a pointer. Any changes you make to ListNode (making it point at something else) will affect the variable that was passed to the function.

If you remove this, the recursive calls, e.g. BinaryTree *leftChild = sortedListToBST(list, start, mid-1);, will modify a copy of list instead of the actual list, and the code will behave differently.

The & is required so that you can modify the pointer passed from the caller code in such way that the caller code will see the change - the pointer is passed by reference, not by value.

If you pass it by value (no &) the caller will not see the changes, because the called function will get a copy of the passed pointer and that copy will be discarded.

I'm not sure whether this is critical for this specific code.

In the first case, ListNode *& is passing a reference to a ListNode. The statement list = list->next affects the caller's pointer.

This is used in the first function so that there would be no need to explicitly advance the list pointer before going into the right half of the sort. Otherwise you would have to have the list pointer advance by (n/2) before going into the right half of the sort.

As far as the second function is concerned, the argument is not a reference, so that the games played by sortedListToBST dont actually change the head pointer.