109题求解。为何需要 pre 这个变量呢？

代码如下，可以运行。为何需要 第21行 的 pre，我看了半天没有看懂。求解～

1. class Solution {
   
2.    
   
3.     public TreeNode sortedListToBST(ListNode head) {
   
4.    
   
5.         if(head == null) return null;
   
6.         
   
7.         ListNode mid = this.findMid(head);
   
8.         
   
9.         TreeNode T = new TreeNode(mid.val);
   
10.          
    
11.         if(head == mid) return T;
    
12.          
    
13.         T.left = this.sortedListToBST(head);
    
14.         T.right = this.sortedListToBST(mid.next);
    
15.         
    
16.         return T;
    
17.     }
    
18.    
    
19.     public ListNode findMid(ListNode node){
    
20.         
    
21.         ListNode pre = null;
    
22.         
    
23.         ListNode slow_Ptr = node;
    
24.         ListNode fast_Ptr = node;
    
25.         
    
26.         while(fast_Ptr!=null && fast_Ptr.next != null){
    
27.             
    
28.             pre = slow_Ptr;
    
29.             
    
30.             slow_Ptr = slow_Ptr.next;
    
31.             fast_Ptr = fast_Ptr.next.next;
    
32.             
    
33.         }
    
34.         
    
35.         if(pre != null) pre.next = null;
    
36.               
    
37.         return slow_Ptr;
    
38.     }     
    
39. }

复制代码

把链表断开？

这个pre的作用就是为了将原list从中间切开，即pre.next=null.

这样做的原因是只有这样才能将原问题转化为一个封闭的子问题（每次递归call sortedlisttobst只处理原list的一半）

注意当给定一个单链表head时，这里的默认终止节点就是next==null，必须利用这个才能找到mid node. 那么在构建子问题也必须严格保证所有原问题的假设。在这里后半个list自动保证终结；但前半个list只能手动“切断”。

这些特殊处理主要就是由于单链表的不对称性造成，即找下个节点易，但找前个节点难。这也是为什么面试中大部分链表都是单链表，而很少涉及双链表（那样就问题就不够有趣）

同时若该题扩展为sorted array to bst, 那么每次递归的函数参数就得同时给起止indexes, 而单链表只给head 就是因为tail的特征被“无情的”隐含了。

pre的作用体现在第35行
目的是把单向链表(从中间)打断

是的学习了。谢谢各位