LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

지금까지 풀었는 링크드리스트 문제들과 마찬가지로 문제의 제한 사항에 “You must solve the problem in O(1) extra space complexity and O(n) time complexity.”가 존재한다. 즉 링크드리스트를 다른 자료형으로 바꾸지 말고 그대로 활용해서 풀라는 뜻이다.

이 문제는 상대적으로 간단하다. 기존의 리스트를 끝까지 순회하면서 홀수 node는 이전 홀수 node의 next에 짝수 node는 이전 짝수 node의 next에 연결해서 각각 2개의 별도의 리스트를 만들다. 그런 다음에 짝수 node만으로 이뤄진 리스트를 홀수 node만으로 이루어진 리스트에 연결해주면 된다.

나머지 설명은 코드의 주석으로 갈음한다.

코드

class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        // 각각 홀수 node, 짝수 node로 이루어진 별도의 링크드리스트를 만든다.
        var odd = head // 홀수 node로만 이루어진 링크드리스트의 head
        var even = head?.next // 짝수 node로만 이루어진 링크드리스트의 head
        
        // odd 리스트에 뒤에 연결하기 위해서 even의 head는 따로 저장
        let evenHead = even
        
        while true {
            // odd 리스트 뒤에 홀수 번째 node (even의 next) 연결
            odd?.next = even?.next
            // even 리스트 뒤에 짝수 번째 node (evendml next, next) 연결
            even?.next = even?.next?.next
            
            // 더 이상 odd의 next -> 즉 홀수 node가 없다면 break
            if odd?.next == nil { break }
            
            // 아니라면 다음 홀수, 짝수 node로 이동
            odd = odd?.next
            even = even?.next
        }
        
        // odd 리스트에 even 리스트를 연결
        odd?.next = evenHead
        
        return head
    }
}