문제

→ 주어진 연결 리스트를 홀수번째 값을 앞쪽에 짝수번째 값을 뒤쪽에 배치하라

→ 공간 복잡도 O(1), 시간복잡도 O(n)에 풀이할 것.

→ 입력값 : [1, 2, 3, 4, 5] / 출력값 [1, 3, 5 ,2, 4]

접근 방법

내가 풀었던 방식은 연결리스트를 리스트화시켜 파이썬 슬라이싱 기법을 사용했으나 공간복잡도와 시간복잡도

제약을 해결하지 못했다.

해설 참조

→ 핵심 홀수와 짝수의 헤더 지정

코드

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