“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/odd-even-linked-list/
연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하는 문제다. 제약 사항으로 공간 복잡도 O(1)과 시간 복잡도 O(n)을 지켜야 한다.
노드 값이 홀짝인가를 보면 되는 줄 알았더니 노드의 순서를 말하는 것이었다. [2,1,3,5,6,4,7]을 [2,3,6,7,1,5,4]로 만들면 된다.
지금까지 해왔던 문제와 크게 다르지는 않았다. 노드와 노드의 next를 어떻게 치환하는가가 헷갈리는 문제이다.
def oddEvenList1(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
odd = head
even = head.next
even_head = odd.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홀수 노드이든 짝수 노드이든 해당 노드의 next를 next.next로 바꾸고, 해당 노드를 next로 바꾸어 가는 것으로 반복한다. 마지막으로 짝수 노드의 첫 노드(even_head)를 홀수 노드의 next로 연결해서 반환하면 된다.
while의 조건문 even and even.next를 이해하기 위해서 손으로 흐름을 그려봐야 했다. 리스트의 전체 길이가 홀수인 경우 짝수 노드의 마지막 반복이 None -> None이 되므로 even과 even.next가 None이어서는 안 된다. ([1,2,3,4,5]의 경우 홀수 노드 5->None을 연결할 때 짝수 노드는 None->None을 연결하려 하므로)
그렇게 어렵지 않은 문제인데 괜히 위축 돼서 풀이를 좀 참고하고 말았다.