[LeetCode]题解（python）：143-Reorder List

题目来源：

　　https://leetcode.com/problems/reorder-list/

---

题意分析：

　　给定一个链表L：L0→L1→…→Ln-1→Ln，改变链表的排序为： L0→Ln→L1→Ln-1→L2→Ln-2→…，要求时间复杂度为O（n），不能改变节点的值。

---

题目思路：

　　题目思路是把链表拆成两个长度相等的链表，然后将后面的链表翻转，重新连起来。

---

代码（python）：

 # Definition for singly-linked list.

 # class ListNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.next = None

 class Solution(object):

     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 or head.next.next == None:

             return

         slow = fast = head

         while fast and fast.next:

             slow = slow.next

             fast = fast.next.next

         head1,head2 = head,slow.next

         slow.next = None

         tmp = ListNode(0)

         tmp.next,p = head2,head2.next

         head2.next = None

         while p:

             tmp1,p = p,p.next

             tmp1.next = tmp.next

             tmp.next = tmp1

         head2 = tmp.next

         while head2:

             tmp2,tmp3 = head1.next,head2.next

             head1.next = head2

             head2.next = tmp2

             head1,head2 = tmp2,tmp3