# Leetcode: Reorder List

Reorder List Similar Problems:

Given a singly linked list L: L0 -> L1 -> … -> Ln-1 -> Ln,
reorder it to: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> …

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/reorder-list
## Basic Ideas:
##             Find the right sub-list after n/2 node
##             Reverse the right sub-list
##             Insert it into the sub-list one by one
## Complexity: Time O(n), Space O(1)
##
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
"""
return

length = 0
while p:
length += 1
p = p.next
for i in xrange(length/2):
p = p.next

# reverse sub-list after p
q = p.next
p.next = None
while q:
r = q.next
q.next = p.next
p.next = q
q = r

# insert the right-sub list to the left-sub list