ch8 328 홀짝 연결 리스트

• 문제
• 풀이
  • 반복 구조로 홀짝 노드 처리
    • 생각
    • 책 풀이

문제

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

풀이

반복 구조로 홀짝 노드 처리

생각

• 홀수 노드와 짝수 노드를 각각 모아서 처리한 후 나중에 이어붙인다

책 풀이

"""
INPUT:  1    2    3    4    5
OUTPUT: 1    3    5    2    5
"""
def oddEvenList(self, head: ListNode) -> ListNode:
    if head is None:
        return None
    # 홀수만 모으기 위한 헤드
    # 1 -> 2 -> 3 -> 4 -> 5
    odd = head
    # 짝수만 모으기 위한 헤드
    # 2 -> 3 -> 4 -> 5
    even = head.next
    even_head = head.next

    while even and even_head:
        # 짝수번째에 다음 홀수번째 값을 할당한다
        # - odd.next = 1 -> 3 -> 4 -> 5
        #   - odd.next = 5
        odd.next = odd.next.next
        # 다음 홀수번째 노드로 이동
        # - odd = 3 -> 4 -> 5
        #   - odd = 5
        odd = odd.next
        # - even = 2 -> 4 -> 5
        #   - even = 4 -> None
        even.next = even.next.next
        # 다음 짝수번째 노드로 이동
        # - even = 4 -> 5
        #   - even = None
        even = even.next

    # 짝수번째 노드만 모은 헤드를 붙인다
    odd.next = even_head

    return head