Odd Even Linked List (Linked List)

LeetCode의 Odd Even Linked List 문제다.

Odd Even Linked List - LeetCode

연결 리스트가 주어졌을 때 홀수 번째의 노드와 짝수 번째의 노드끼리 묶어서 홀수 노드들 다음에 짝수 노드들이 오도록 재구성하는 문제다. 즉 노드 1, 노드 2, 노드 3, 노드 4, 노드 5가 있다면 노드 1, 노드 3, 노드 5, 노드 2, 노드 4로 다시 구성돼야 한다.

간단하게 생각한다면 그냥 연결 리스트를 탐색하면서 홀수 노드, 짝수 노드를 어디 저장해뒀다가 나중에 합치는 방식으로 생각할 수 있겠지만 문제에서 O(1) 공간 복잡도를 요구하기 때문에 연결 리스트의 연결 자체를 바꾸는 식으로 풀이해볼 수 있겠다.

 

내가 생각한 풀이 방법은 노드를 두 개씩 다루는 방법이었다. 그래서 홀수 번째(i) 노드, 짝수 번째(i+1) 노드가 있다면 홀수 번째 노드를 다음 홀수 번째(i+2) 노드와 연결시키고 짝수 번째 노드도 다음 짝수 번째(i+1+2) 노드와 연결시키면서 홀수 노드, 짝수 노드끼리 모으는 방법으로 구현하였다.

 

물론 이렇게 끼리끼리 이은 후에는 맨 마지막 홀수 노드의 다음 노드로 짝수 노드를 이어줘야 하기 때문에 맨 처음 짝수 노드는 별도의 변수에서 기억해야 했다. 이를 제외하면 별다른 로직은 없었다.

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # at least two nodes
        if head is None:
            return head
        
        # process odd nodes
        oddNode, evenNode, firstEvenNode = head, head.next, head.next
        
        while evenNode and evenNode.next:
            # 홀수 노드, 짝수 노드의 다음 노드를 다음 다음 노드로 설정 후 이동.
            oddNode.next, evenNode.next = oddNode.next.next, evenNode.next.next
            oddNode, evenNode = oddNode.next, evenNode.next
        
        # 마지막 홀수 노드의 다음 노드를 첫번째 짝수 노드로 설정.
        oddNode.next = firstEvenNode    
        return head

파이썬의 동시 할당 기능을 사용하여 어렵지 않게 풀 수 있었다.