Leetcode1669.MergeInBetweenLinkedLists

소스코드

문제

• 1669.MergeInBetweenLinkedLists

풀이 (brute-force)

• 상세 풀이 주석
• 시간 복잡도 O(n)

/**
     * 1. 문제
     *  - listNode1, 2 가 주어짐.
     *  - listNode1 의 a,b 번째를 삭제한다.
     *  - 그 사이에 listNode2 를 채운다.
     *
     * 제약 조건
     * 3 <= list1.length <= 104
     * 1 <= a <= b < list1.length - 1
     * 1 <= list2.length <= 104
     *
     * 2. 풀이 (brute-force)
     *  - list1 을 순회하면서 ListNode result 에 추가한다.
     *  - list1 a 를 만나면 list2 를 result 에 추가한다.
     *  - list1 b 까지 순회하고, 나머지를 result 에 추가한다.
     *  - 시간복잡도 O(n)
     *
     */
    fun mergeInBetween(
        list1: ListNode,
        a: Int,
        b: Int,
        list2: ListNode
    ): ListNode {
        // a 는 1이상이니 list1[0] 인덱스를 처음에 넣어준다.
        val result = ListNode(list1.`val`)
        // tail 은 항상 result 의 마지막 next 를 가리켜야 함. tail 을 사용하는 이유는 매번 끝까지 조회하는 것은 비용이 크기 때문
        var tail = result
        // idx 는 listnode1 의 index 를 의미. a 는 1이상이니 idx 는 1부터 시작
        var idx = 1

        // list1 의 current listnode
        var current = list1

        // list1 을 순회하면서 list2 를 넣는다.
        while (current.next != null) {
            // list2 를 추가할 조건
            if (a <= idx && idx <= b) {
                // 마지막을 list2 에 연결시켜줌
                tail.next = list2
                // 마지막은 list2 의 마지막을 가리켜야 함
                tail = getLastListNode(list2)
                // a 부터 b 까지 제거할 예정이니 b+1 까지 current 를 순회
                while (idx <= b) {
                    current = current.next!!
                    idx++
                }
            }

            // tail.next -> result 마지막 next 가리킴
            tail.next = ListNode(current.next!!.`val`)
            // tail.next 는 result 마지막의 next 의미. 그것을 다시 tail 붙여서 result 마지막 next 를 가리킴
            tail = tail.next!!

            current = current.next!!
            idx++
        }
        return result
    }

    // listNode 마지막 return
    fun getLastListNode(listNode: ListNode): ListNode {
        var tmp = listNode
        while (tmp.next != null) {
            tmp = tmp.next!!
        }
        return tmp
    }