소스코드

문제

풀이 (brute-force)

  • 방향성은 single list -> 순환 list 를 만든 뒤, 특정 지점에서 순환을 끊는 것이다.
  • 시간 복잡도 O(n)
  • 상세 설명은 주석
    fun rotateRight(head: ListNode?, k: Int): ListNode? {
        // null 과 0 을 체크
        if (head == null || k == 0) {
            return head
        }

        var copy = head
        var size = 1
        var tail: ListNode?

        // 크기
        while (copy?.next != null) {
            copy = copy.next
            size++
        }
        // tail 용도는 순환구조를 만들기 위함
        tail = copy

        val rotate = k % size
        // 회전을 nodeSize 만큼 수행하면 원점
        if (rotate == 0) {
            return head
        }


        // 회전 후, 시작지점 찾기
        copy = head
        for (i in 0 until size - rotate - 1) {
            copy = copy?.next
        }

      	// 이 부분이 어려움 순환 구조를 만든 뒤, 순환구조를 끊는 부분
        // [1,2,3] k = 2 라 가정
        tail?.next = head // 순환   
        val newHead = copy?.next    // copy.next 는 2 를 가리킴. newHead 는 2, 3
        copy?.next =
            null   // copy 는 1번을 가리키고, copy.next 는 2번을 가리키고 있음. newHead 2 -> 3 -> 1 -> copy.next = null 로 해서 순환을 끊는거임

        return newHead
    }