홀짝 연결 리스트

홀짝 연결 리스트

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재 구성 하라.

제약조건

• 공간복잡도 O(1)
• 시간 복잡도 O(n)

---

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def print_all(self):
        while self:
            print(self.val, end=' ')
            self=self.next
        print()


def oddEvenList( head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:        #예외처리
        return None
    odd = head
    even = head.next
    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 head

---

아이디어

공간 복잡도가 O(1)이므로 새로운 리스트 노드를 생성할 수 없다.

홀수번째 노드는 홀수번 째 노드를 가르키고 짝수 번째 노드는 짝수번째 노드를 가리키게 하고 마지막 홀수번째를 짝수번째 처음 노드를 가리키게 한다.

---

풀이

홀수 변수는 head이고, 짝수 변수는 head.next이다

while문의 결과

	1	2	3
홀수	1 -> 3	3 -> 5	5
짝수	2 -> 4	4 -> None	None