328. Odd Even Linked List

Linked List 순서를 홀,짝으로 구분해서 홀수 먼저 출력하고, 이후 짝수를 출력하는 문제

 

예를 들어, 1->2->3->4->5->NULL이면 홀수 자리는 1->3->5가 있고, 짝수 자리는 2->4가 있다, 

따라서 결과 값은 1->3->5->2->4->NULL

 

1) 홀수와 짝수를 구분하여 넣는 Linked List를 만들고

2)홀수 마지막과 짝수 처음을 연결한다. 

 

그림으로 설명을 해보면, 

처음 odd와 even이라는 ListNode에 각 첫번째 홀수와 짝수 자리를 가르키도록 한다. 

 

 

반복문이 진행때마다 2칸씩 건너뛰면서 다음 자료를 가르키도록 만들면 된다. 

1) 처음에는 odd, even만 있고, while문을 통해서 계속 해서 연결해나간다. 

2) 마지막에 odd와 even_first를 연결한다.

    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        odd = head
        even = head.next
        even_head = head.next

        while even and even.next:
            odd.next = odd.next.next
            even.next = even.next.next
            
            odd = odd.next
            even = even.next
        
        odd.next = even_head
        
        return head