[파이썬 알고리즘] 홀짝 연결 리스트

홀짝 연결 리스트

리트코드로 풀러 가기

연결 리스트를 홀수 번째 노드 다음에 짝수 번째 노드가 오도록 재구성하라.
공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

(다른 말로, 홀수 번째 노드만 모아서 먼저 출력하고 다음에 짝수 번째 노드를 출력하라)

예제 1)
입력: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
출력: 1 -> 3 -> 5 -> 2 -> 4 -> NULL

예제 2)
입력: 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 -> NULL
출력: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4 -> NULL

---

code: oddEvenList.py

이 문제는 직관적으로 생각했을때, 반복하며 홀수번째의 노드를 붙이고, 다음에 짝수 번째의 노드를 붙이거나, 리스트로 자료구조를 바꾸어서 풀면 된다고 생각할 수 있지만 제약사항이 있다.

반복 구조를 이용한 홀/짝 노드 처리

요구된 공간 복잡도가 O(1) 이므로, 새로운 리스트 노드를 생성하여 붙여나갈 수 없다.

따라서 기존에 주어진 head 노드를 이용하여 odd 와 even 노드를 계산한 뒤, 홀수 번째와 짝수 번째의 노드끼리 묶어준다.

해당 작업이 끝난 뒤, 홀수 번째의 노드 마지막에 짝수 번째의 노드 첫번째를 붙여주면 답이 된다.

def oddEvenList(self, head):

    if not head:
        return head

    odd = odd_root = head
    even = even_root = head.next

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

        even.next = even.next.next
        even = even.next

    odd.next = even_root

    return odd_root

역시 처음의 예외 처리는 중요하다.