LC143. Reorder List

Approach 1: Queue

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        q = deque()
        curr = head
        while curr:
            q.append(curr)
            curr = curr.next
 
        # Dummy head to simplify
        head = ListNode()
        i = 0
        while q:
            if i % 2 == 0:
                head.next = q.popleft()
            else:
                head.next = q.pop()
 
            head = head.next
            i += 1
        
        head.next = None
 

Complexity

Time: $O(n)$
Space: $O(n)$

Notes

Other Languages