# 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)
##
# 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 is None or head.next is None or head.next.next is None:
return

length = 0
p = head
while p:
length += 1
p = p.next
p = head
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
p1 = head
p2 = p.next
p.next = None

while p2:
r = p2.next
p2.next = p1.next
p1.next = p2
p1 = p1.next.next
p2 = r
```

Share It, If You Like It.