Leetcode 143 链表对折

思路：

1. 通过快慢指针，一个步长为1， 一个步长为2， 找到链表中点。

2. 前/后 半段链表反转。

3. 与另一半链表归并插入。

class Solution:
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if head == None or head.next == None:
            return
 
        pre = head
        lat = head.next
        while lat != None and lat.next != None:
            pre = pre.next
            lat = lat.next.next
 
        p = pre.next
        pre.next = None
        # reverse
        
        cur = None        
        while p != None:
            q = p.next
            p.next = cur
            cur = p 
            p = q
               
        pre = head
        while pre != None and cur != None:
            tmp = cur.next  
            cur.next = pre.next
            pre.next = cur
            pre = pre.next.next
            cur = tmp