老师您好，我在leetcode上有一道解决不了的链表转二分搜索树问题一直解决不了希望您能给看一下。
来源：5-1 链表，在节点间穿针引线 Reverse Linked List
江月枫鱼
2018-04-21
class Solution {
public:
TreeNode* __changeintoBST (ListNode*&head, int l, int r)
{
if (l>r) return NULL;
int mid = (r-l)/2+l;
TreeNode* templeft= __changeintoBST (head, l, mid-1);
TreeNode* root = new TreeNode(head->val);
head = head->next;
root->left = templeft;
root->right = __changeintoBST (head, mid+1, r);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
if (head==NULL) return NULL;
int len = 0;
ListNode *temp = head;
while (temp!=NULL) {
len++;
temp = temp->next;
}
return __changeintoBST( head, 0, len-1 );
}
};题号是leetcode 109 老师为什么第一个函数递归的时候非要写成*&head啊，*head就会一直错，这和引用有关吗？我觉得没引用也对啊，毕竟我是通过head=head->next做的？希望老师解答
写回答
1回答
-
可能结合int&理解更容易些。在__changeintoBST中，head的改变是要被记住的，传给原来的调用继续使用的，所以要使用引用。head是一个ListNode*型的引用，写作ListNode*&。
通过程序的7,8行可以看出这一点：
在第7行，head还是l位置的ListNode;
第8行，head->val被作为root的值，此时head已经是mid位置的ListNode了，已经不是原来的那个head了，因为__changeintoBST的head传的是引用，在递归调用中被__changeintoBST改变的head被保存下来了。
以上为直观解释。不过依然是，要想理解透彻程序的运行机制，建议用一个小数据量（这个题目给的测试用例就很好），一句一句跟一遍，看一下每一句话运行后，程序的数据是怎样变化的，是怎样一步一步达到最后的结果的。然后，最好再把引用去掉，再跟踪一遍，观察一下此时和加入引用有什么区别，为什么产生这样的区别：）
加油！
132018-04-22
相似问题