Python 알고리즘 인터뷰 - 문제18. 홀짝 연결 리스트

leetcode 328. Odd Even Linked List

 

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

 

예제1

입력

1->2->3->4->5->None

 

출력

1->3->5->2->4->None

 

예제2

입력

2->1->3->5->6->4->7->None

 

출력

2->3->6->7->1->5->4->None

 

풀이

공간 복잡도에 대한 제약이 없으면 LinkedList를 list로 변환한 후 홀수, 짝수 슬라이싱을 각각 이어 붙힌 후 역으로 LinkedList를 만들면 된다. 여기에는 공간복잡도에 대해 명시해 있으니 해당 편법은 쓰지 않고 노드의 연결을 바꾸는 방식으로 진행한다.

 

먼저 odd = head, even = head.next로 포인터를 설정 후 2개의 노드씩 이동하면서 연결을 진행한다.

 

짝수, 홀수별 노드의 연결 후 odd, even 포인터를 이동시킨다.

연결 및 이동은 even, even.next가 None이 아닐 때까지 진행하며 코드는 다음과 같다.

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

 

노드 연결이 끝나면 odd 노드에서 even 노드의 시작점을 연결한다. 처음 포인터를 초기화할 때 even_head = even으로 설정하여 odd를 even_head에 향하게 한다.

 

전체 코드는 다음과 같다.

def oddEvenList(self, head):
    if head is None:
        return head

    odd = head
    even = head.next
    even_head = even

    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

 

head가 None인 경우 even = head.next를 초기화할 때 예외가 발생하므로 예외처리를 해준다.