문제

https://leetcode.com/problems/odd-even-linked-list/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

The first node is considered odd, and the second node is even, and so on.
연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라.
공간 복잡도 O(1), 시간복잡도 O(n)에 풀이하라

풀이

내 풀이

책 풀이랑 거의 똑같이 푼 것 같다.
공간복잡도가 O(n)이라 새로운 연결리스트로 홀수, 짝수 나눈게 아니라
원래 있던 연결리스트에 값을 계속 업데이트 해주었다.
->98 ms

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

        odd = odd_head = head
        even = even_head = head.next

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

        odd.next = even_head

        return odd_head