LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

처음에 이 문제를 읽으면 가장 간단한 방법으로 떠올리는 것이 링크드리스트를 Array로 바꾼 다음 그 Array를 뒤집어서 다시 링크드리스트로 만드는 방법이다. 하지만 링크드리스트를 Array 같은 익숙한 자료형으로 변경해서 푸는 작업은 시간과 메모리에서 보는 손실이 많다.

단방향 링크드리스트를 뒤집는 법은 간단하게 말하면 2개의 연속된 node의 순서를 바꾸어주면서 1칸씩 이동하는 방법이다. 앞노드를 뒷노드의 next로 할당하는 작업을 리스트 끝까지 반복해서 수행하면 된다.

이를 구현하는 방법은 재귀함수를 활용하는 법과 반복문을 활용하는 법 2가지가 존재한다.

반복문를 활용하는 법

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        // node: 현재 node
        // prev: 현재보다 앞에 있는 node
        var node = head, prev: ListNode? = nil
        
        // 1칸씩 앞으로 이동하면서 prev를 node.next에 연결하고
        // prev에 node를 prev에 node.next를 할당한다.
        while node != nil {
            let next = node?.next
            node?.next = prev
            prev = node
            node = next
        }
        
        // node == nil이 되면 (마지막 node를 지남)
        // prev (= 기존 링크드리스트의 마지막 node)가 뒤집힌 링크드리스트의 head가 된다.
        
        return prev
    }
}

재귀함수를 사용하는 법

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        // node와 prev를 받아서 node의 next를 prev로 바꾸어주는 함수
        func reverse(_ node: ListNode?, _ prev: ListNode?) -> ListNode? {
            // node == nil (list의 마지막에 도달하면) prev를 리턴
            if node == nil { return prev }
            let next = node?.next
            // prev를 node의 next에 할당한다
            node?.next = prev
            // 기존의 next를 node자리에, 기존의 node를 prev 자리에 넣어서 다시 실행한다.
            return reverse(next, node)
        }
        return reverse(head, nil)
    }
}