leetcode--Reorder List--ポイントは、面接問題としてふさわしいです。

https://leetcode.com/problems/reorder-list/
コード1
参照http://bookshadow.com/weblog/2015/01/29/leetcode-reorder-list/
考え方：1.速い針でチェーンの中の点midを見つけて、チェーンの表を左右の半分に分けます。チェーンの右の部分を定位置で逆置します。チェーンの左右の部分を結合します。（左と右のすべての要素を通り抜けます。）

class Solution(object):
    def reorderList(self, head):
        """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """
        if head and head.next and head.next.next:

            #find mid
            slow = head
            fast = head
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            mid = slow

            #cut in the mid
            left = head
            right = mid.next
            if right is None:
                return head
            mid.next = None

            #reverse right half
            cursor = right.next
            right.next = None
            while cursor:
                next = cursor.next
                cursor.next = right
                right = cursor
                cursor = next

            #merge left and right
            dummy = ListNode(0)
            while left or right:
                if left is not None:#       
                    dummy.next = left
                    left = left.next
                    dummy = dummy.next
                if right is not None:# dummy        
                    dummy.next = right
                    right = right.next
                    dummy = dummy.next

私の再帰アルゴリズムはTLEタイムアウトです。

class Solution(object):
    def reorderList(self, head):
        """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """
        if not head or not head.next or not head.next.next: return head

        cur = head
        dummy = ListNode(0)
        dummy.next = head
        pre, last = dummy, head
        while last.next:
            pre = last
            last = last.next
        pre.next = None
        tmp = cur.next
        cur.next, last.next = last, tmp
        self.reorderList(tmp)

コード2
問題解決の考え：1、まずチェーンを二つの等しい長さのチェーンに切ります。チェーンの長さが奇数なら、第一のチェーンの長さは1より多いです。元のチェーンがL={1,2,3,4,5}だったら、分割結果はL 1={1,2,3}です。L 2={4,5}分解の技術は、やはり、針を速くする技術です。
2は、L 2={4,5}をL 2={5,4}に反転させるように、第2のチェーンL 2を反転させます。

          3，        。

http://www.cnblogs.com/zuoyuan/p/3700846.html