老师您好，我在leetcode上有一道解决不了的链表转二分搜索树问题一直解决不了希望您能给看一下。

Question

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做的？希望老师解答

Answer 1

liuyubobobo 2018-04-21 13:12:07

可能结合int&理解更容易些。在__changeintoBST中，head的改变是要被记住的，传给原来的调用继续使用的，所以要使用引用。head是一个ListNode*型的引用，写作ListNode*&。

通过程序的7,8行可以看出这一点：

在第7行，head还是l位置的ListNode;

第8行，head->val被作为root的值，此时head已经是mid位置的ListNode了，已经不是原来的那个head了，因为__changeintoBST的head传的是引用，在递归调用中被__changeintoBST改变的head被保存下来了。

以上为直观解释。不过依然是，要想理解透彻程序的运行机制，建议用一个小数据量（这个题目给的测试用例就很好），一句一句跟一遍，看一下每一句话运行后，程序的数据是怎样变化的，是怎样一步一步达到最后的结果的。然后，最好再把引用去掉，再跟踪一遍，观察一下此时和加入引用有什么区别，为什么产生这样的区别：）

加油！

• 提问者 江月枫鱼 #1

  谢谢老师！虽然还是迷迷糊糊的但是好像能够明白一点了，没想到真的能得到老师的回复！我也是ACMer，再次谢谢老师的回答！

• liuyubobobo 回复 提问者 江月枫鱼 #2

  主要是因为C++不能方便的返回两个不同的结果。在这里，他其实希望的是返回TreeNode和下一个要考虑的ListNode两个结果。如果觉得这个引用太不好理解，可以参考我的这个解答。其实复杂度稍微高一些，但没有复杂度量级的变化，都是O(n)的：）https://github.com/liuyubobobo/Play-Leetcode/blob/master/0109-Convert-Sorted-List-to-Binary-Search-Tree/cpp-0109/main.cpp ACMer非常赞！预祝取得好成绩。前途大大的！

• 提问者 江月枫鱼 回复 liuyubobobo #3

  嗯嗯，谢谢老师⊙∀⊙！