LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

링크드리스트를 뒤집는 문제이다. 다만 링크드리스트의 모든 node의 순서를 뒤집는 것이 아니라 중간에 일정 구간만 뒤집어야 한다. 나는 중간에 뒤집어야 하는 링크드리스트를 일단 뒤집은 이후에 기존의 앞뒤에 있는 node에 다시 붙이는 방법을 사용했다. 다만 주의할 점은 left가 1인 경우는 답을 리턴할 때 기존의 head를 리턴하면 안된다는 것이다. (head가 뒤집힌 링크드리스트의 일부이므로 이미 뒤로 이동한 상황이다.) 자세한 풀이는 코드의 주석을 참고하기 바란다.

코드

class Solution {
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        // 순서를 바꾼 결과물의 head를 리턴하기 위해서 따로 변수로 저장한다.
        let ans = head
        
        // left 보다 한칸 왼쪽에 있는 node를 찾는다.
        var i = 1
        var beforeLeft: ListNode? = ListNode(0, head)
        while i != left {
            beforeLeft = beforeLeft?.next
            i += 1
        }
        
        // 순서를 뒤집을 SubList의 왼쪽 끝 node (-> 뒤집으면 오른쪽 끝이 됨)
        let leftNode = beforeLeft?.next
        
        // 뒤집을 SubList의 오른쪽 끝을 찾는다. (-> 뒤집으면 왼쪽 끝이 됨)
        var rightNode = leftNode
        while i != right {
            rightNode = rightNode?.next
            i += 1
        }
        
        // right보다 한칸 오른쪽에 있는 node
        let afterRight = rightNode?.next
        
        // now와 prev를 사용해서 SubList를 뒤집는다.
        var now = leftNode, prev: ListNode? = nil
        for _ in 0..<(right - left + 1) {
            let next = now?.next
            now?.next = prev
            prev = now
            now = next
        }
        
        // 뒤집힌 SubList를 왼쪽 끝과 오른쪽 끝에 연결한다.
        beforeLeft?.next = rightNode
        leftNode?.next = afterRight
        
        // left가 1이면 head의 순서가 바뀌어 있으므로
        // 순서가 바뀐 리스트의 head가 된 rightNode을 리턴한다.
        return left != 1 ? ans : rightNode
    }
}

짧은 풀이

좀 더 코드를 줄일 수 있는 방법은 뒤집어야 하는 리스트의 끝을 찾는 대신에 “뒤집어야 하는 리스트의 시작점 (= 아래 그림에서 2, 코드에서 start)”를 right - left번 뒤로 한칸씩 이동시키면서 start에 뒤에 있는 node를 before의 뒤로 이동시키는 것이다. 1번 코드를 실행할 때마다 아래 빨간 화살표처럼 before의 뒤에 start.next를 그리고 start.next의 뒤에 end를 그리고 마지막에 기존의 start.next.next였던 after를 연결하는 방식이다.

end는 before의 next로 갱신되어야 하며 start는 고정이다. 나머지는 코드와 그림으로 갈음한다.

class Solution {
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        let ans = head
        
        var i = 1
        var before: ListNode? = ListNode(0, head)
        while i != left {
            before = before?.next
            i += 1
        }
        
        // start = 뒤집을 리스트의 시작점 (뒤집히면 맨 뒤로 가야함)
        // end = 뒤집을 리스트의 끝점 (뒤집히면 맨 앞으로 가야함)
        var start = before?.next, end = start
        
        for _ in 0..<(right - left) {
            let after = start?.next?.next // after 변수 할당
            before?.next = start?.next // 빨간 화살표 1
            start?.next?.next = end // 빨간 화살표 2
            start?.next = after // 빨간 화살표 3
            
            end = before?.next // end 갱신
        }
        
        // left가 1이면 head의 순서가 바뀌어 있으므로
        // 순서가 바뀐 리스트의 head가 된 rightNode을 리턴한다.
        return left != 1 ? ans : end
    }
}