排序清單轉換為二分查找樹

題目描述：給出一個所有元素以升序排序的單連結清單，将它轉換成一棵高度平衡的二分查找樹

我們之前做過一道将排序數組轉換為二分查找樹的問題，詳見：點選打開連結

将連結清單轉換為二分查找樹與上面這道題的基本思想一模一樣（在這裡，高度平衡，也就是高度最小），是以我們要解決的問題就是查找到排序連結清單的中值，作為根節點，然後将連結清單分割，分别按照同樣的思想生成左右子樹。（如果對這個算法有疑問，請先搞懂我剛才給出的連結的那道題）

那麼如何查找連結清單的中值呢？當然不能全周遊一遍，再回溯。這方法效率太低，我在這裡給出一種通用的“快慢指針法”

我假設看我這篇文章的人對連結清單的基本結構已經很熟悉了。那麼現在可以設定兩個指針slow和fast，我們令這兩個指針一開始都指向連結清單的頭結點--head，然後slow每次指向連結清單的下一位（就是它現在所指向的節點的next），而fast每次指向他的下一位的下一位（也就是每次向後移動兩個節點），那當fast指向尾節點的時候，slow指向的剛好是中間節點。

舉個例子：1->2->3->4->5

1. 一開始，slow,fast都指向1

2. slow移動一位，指2；fast移動兩位，指3

3. slow接着移動一位，指3；fast接着移動兩位，指5. 此時fast指向尾節點，slow剛好指向中間節點。

這是快慢指針的基本應用，當然具體處理問題的時候，快慢指針會根據具體問題做相應修改，是以，一定要靈活運用。

就拿這道題來說吧，按照上面的快慢指針法，當然能找到中間節點，但是，随後我們是要對連結清單分割的，而隻有知道中間節點之前的那個節點，才能實作“摘鍊”（就是把連結清單的一部分“摘”下來，形成單獨的連結清單）

是以，此處也有個通用的技巧，就是在連結清單的頭結點之前人為的放置一個dummy節點幫助我們處理問題。還是上面的那個例子，當放置了dummy節點之後，就變成下面這個樣子了：

dummy->1->2->3->4->5

可以令slow初始時指向dummy，fast初始時指向head，還是剛才那樣掃描連結清單，發現當fast指向尾節點時，slow剛好指向2，正好在中間節點前面。我們就能實作摘鍊了。

是以，這個題的思路沒什麼值得注意的，倒是對連結清單的操作，是需要學習的。

代碼可以給出了：

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param head: The first node of linked list.
    @return: a tree node
    """
    def sortedListToBST(self, head):
        if head is None:
            return None
        # 随意指派給dummy即可
        dummy = TreeNode(-1)
        # dummy連在head前面
        dummy.next = head
        slow, fast = dummy, head
        # 直到fast指向尾巴
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 找到中間節點了，為slow.next
        root = TreeNode(slow.next.val)
        # 以下三行為摘鍊，需注意操作順序
        second = slow.next.next
        slow.next = None
        first = dummy.next
        # 遞歸
        root.left = self.sortedListToBST(first)
        root.right = self.sortedListToBST(second)
        return root
        # write your code here
           

連結清單對于算法設計的意義是什麼呢？我個人的了解：連結清單是樹和圖的基礎，也可以說是一種結構簡單的樹或者圖，而樹和圖能夠形象的刻畫現實問題，這為算法的設計提供了廣闊的空間。