Odd Even Linked List

Odd Even Linked List

• 입력 : 연결리스트, 길이는 0 ~ 10^4
• 출력 : 홀수 번째 Nodes를 앞으로(홀수 번째 Nodes 순서는 유지), 짝수 번째 Nodes는 뒤로 재배치(짝수 번째 Nodes 순서는 유지)
• 조건 : 공간복잡도 O(1) 시간복잡도 O(N)

Solution

• 홀수번째 Node 끼리, 짝수번째 Node 끼리 모으고 마지막에 합치기

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if not head or not head.next: return head

        evenhead = head.next        
        odd, even = head, evenhead        

        while even and even.next:            
            odd.next = even.next            
            even.next = even.next.next                        
            odd, even = odd.next, even.next

        odd.next = evenhead      
        return head