A python solution using deque


  • 0
    D

    Using a double-ended queue is very intuitive. Take node from left end as current node on the odd run, and take node from right end on the even run. Thus we get 1,n,2,n-1,3,n-2.... and link them on the fly

    class Solution(object):
    def reorderList(self, head):
        
        prev,curr = ListNode(0),head
        q = collections.deque()
        while head:
            q.append(head)
            head = head.next
        
        i = 1
        while q:
            if i&1: curr = q.popleft() # if odd, pop from left
            else: curr = q.pop() # in the next run, pop from right
            prev.next = curr
            prev = curr
            i+=1
        if curr: curr.next = None

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.