[Leetcode/Medium] 홀짝 연결 리스트 (328. Odd Even Linked List, Swift)

https://leetcode.com/problems/odd-even-linked-list/

 

🤔 문제 설명

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재정렬하라.

단, 공간 복잡도 O(1), 시간 복잡도 O(n) 안에 문제를 풀어야 한다.

head = [1,2,3,4,5]
// [1,3,5,2,4]

 

💡 풀이

내가 생각한 방법은 이렇다.

1. head 연결 리스트에서 홀수번째에 있는 값은 odd라는 연결 리스트로, 짝수번째에 있는 값은 even이라는 별도의 연결 리스트로 연결을 한다.
2. head 연결 리스트를 반복하면서, 각각 2칸씩 건너뛰면서 연결 리스트를 추가한다. + 이동까지
   (홀수 노드의 경우 : oddNodes.next = oddNodes.next.next / 짝수 노드의 경우 : evenNodes.next = evenNodes.next.next)
3. odd 연결 리스트의 끝 부분과 even 연결 리스트의 첫 부분을 연결하고 반환한다.

이 방법대로 코드를 구성한 것이 아래의 코드이다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 9ms (Beats 95.30%), Memory : 15.94MB (Beats 38.26%)

class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        guard var head else { return head }

        var oddNodes: ListNode? = head          // 홀수번째 있는 노드들
        var evenNodes: ListNode? = head.next    // 짝수번째 있는 노드들
        var evenHead = evenNodes                // 마지막 홀수와 "짝수 시작"부분을 연결하기 위함
        
        while (evenNodes?.next != nil) {
            oddNodes?.next = oddNodes?.next?.next
            oddNodes = oddNodes?.next
            evenNodes?.next = evenNodes?.next?.next
            evenNodes = evenNodes?.next
        }
        
        // 홀수 마지막 노드와 짝수 첫 노드를 연결
        oddNodes?.next = evenHead
        
        return head
    }
}