LeetCode 풀기 - 143. Reorder List

143. Reorder List

https://leetcode.com/problems/reorder-list/

Reorder List - LeetCode

문제)

솔루션1) two deques

두 개의 deque() 자료구조를 사용합니다.

풀이 전략:

•  deque() 자료구조 q1, q2를 준비
• 리스트 전체를 순회해서 모든 값을 q1에 넣음
• q1 아이템에서 뒤의 절반에 해당되는 부분을 pop()해서 q2에 추가
• q1, q2 아이템을 번갈아가면 pop() 하면서 리스트의 값을 업데이트 수행

# 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.
        """        
        q1 = deque()
        q2 = deque()
        
        # traversal        
        cur_node = head        
        while cur_node:
            q1.append(cur_node.val)
            cur_node = cur_node.next
            
        num_of_q1 = len(q1)
        half_num_of_q1 = num_of_q1 // 2        
                
        # move q1 items to q2
        for i in range(half_num_of_q1):
            q2.append(q1.pop())
            
        cur_node = head        
        for item1, item2 in zip_longest(q1, q2):
            if item1:
                cur_node.val = item1
                cur_node = cur_node.next
            if item2:
                cur_node.val = item2
                cur_node = cur_node.next
            
        return head