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