문제 링크 (opens new window)

문제 설명

1. 연결리스트 인덱스가 홀수인 연결 리스트와 짝수인 연결리스트를 구분한 뒤, 홀수 연결리스트 뒤에 짝수 연결리스트를 붙이는 문제이다.
2. 공간복잡도가 O(N)이므로 ListNode객체 생성에는 부담 없음
3. 참조관계만 적절히 설정하면 되는 문제

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        guard let head else { return nil }
        guard let next = head.next else { return head }
        var idx = 1
        var cur: ListNode? = head

        var oddHead = ListNode(head.val)
        var evenHead = ListNode(next.val)

        var oddCur: ListNode? = oddHead
        var evenCur: ListNode? = evenHead

        while(cur != nil) {
            if idx > 2 {
                if idx % 2 == 1 {
                    oddCur?.next = ListNode(cur!.val)
                    oddCur = oddCur?.next
                } else {
                    evenCur?.next = ListNode(cur!.val)
                    evenCur = evenCur?.next
                }
            }

            cur = cur?.next
            idx += 1
        }
        oddCur?.next = evenHead
        return oddHead
    }
}