Reverse Linked List (+LinkedList란?)

Description

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• 5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

들어가기에 앞서 LinkedList란?

LinkedList는 Node로 이루어진 리스트로, 각 노드는 값(value)과 다음 노드에 대한 주소값을 가지고 있다. LinkedList와 같이 일반적을 값의 추가/삭제가 가능한 ArrayList와 비교해보면, ArrayList의 각 값은 인덱스를 가지고 있어 인덱스로 해당 요소를 찾을 수 있는 반면, LinkedList는 각 요소(노드)가 값과 이전/이후 노드에 대한 주소값(포인터)을 가지고 있어 이를 가지고 요소를 찾을 수 있다. 이렇게만 들으면 굳이 LinkedList를 쓸 필요성에 대해 못 느낄 수 있다. 하지만 ArrayList의 동작 원리와 비교해보면 어떤 상황에서 LinkedList가 필요한지 알 수 있다.

ArrayList(선형) vs. LinkedList(연결)

ArrayList는 내부적으로 Array를 사용하는 MutableList(인터페이스) 구현체이다.
ArrayList는 Array를 사용하여 자동으로 크기를 조정하며 값을 추가한다. ArrayList를 생성하면 초기 용량을 가진 Array가 생성된다.(초기 용량은 ArrayList(n) 생성시 인자로 값을 넘겨 설정하거나, 기본 값인 10으로 설정된다.) add()로 ArrayList에 값을 추가하면 내부 배열에 저장 공간이 있는지 확인하여, 있으면 인덱스에 값을 추가한다.
충분한 저장 공간이 없다면 ArrayList는 더 큰, 새로운 내부 배열을 생성해(기존 배열의 두 배 크기로 증가. 추후 새로운 배열을 만드는 횟수를 줄이기 위해 두 배로 증가) 거기에 기존 배열의 값들을 복사해 넣고 새로운 값을 넣는다.
그리고 새 배열이 생성되고 모든 값을 넣으면, 이전의 내부 배열은 폐기해 GarbageCollector가 이전 배열의 메모리를 회수한다.
저장 공간 부족시 더 큰 새로운 배열을 생성해 모든 값을 복사해넣고 새로운 값을 넣는 작업을 반복적으로 하는 것은 많은 비용이 든다. 이러한 작업에서 이점을 가지는 것이 LinkedList이다.

LinkedList는 내부적으로 배열을 쓰고 있지 않으며 노드만 추가하면 되기에, 새로운 값을 추가하는데 추가 저장공간을 위해 Array를 생성하고 값을 옮기는 ArrayList와 같은 과정을 거치지 않는다. 따라서 리스트의 맨 앞이나 뒤에 값을 추가할 때 LinkedList는 O(1)의 시간복잡도를 가진다. 리스트의 중간에 값을 넣을때에는 넣을 위치를 찾아야 하기 때문에 넣을 위치를 찾기까지 O(n)의 시간복잡도를 가질 수 있다. 하지만 리스트의 처음이나 중간에 새로운 값을 넣을때 이후 인덱스의 값들을 한칸씩 뒤로 옮기는 작업을 하는 ArrayList와 달리, LinkedList는 찾은 위치를 기준으로 새로운 노드에 앞뒤 노드를 연결만 하면 되므로 삽입에는 O(1)의 시간복잡도를 갖는다.

ArrayList와 LinkedList의 동작 원리를 통해 미루어볼 수 있듯이, ArrayList는 인덱스로 바로 값에 접근할 수 있기에 탐색에 용이한 자료 구조를 가졌으며, LinkedList는 값을 추가할 때 포지션을 기준으로 앞뒤 노드만 새로 연결해주면 되기에 삽입/삭제에 좀 더 용이한 자료구조를 가졌다.

참고) https://blog.logrocket.com/arraylist-vs-linkedlist-kotlin-data-structure/

Solution

• 위의 LinkedList에 대한 이해를 바탕으로 아래의 ListNode는 next로 다음 노드의 주소를 가지고 있는 LinkedList이다.

• head는 검은색 화살표 방향으로 참조를 가지고 있지만, 우리가 해야할 것은 파란색 화살표 방향으로 next의 참조를 바꾸는 것이다.
• 따라서 prev 값을 두어 각 노드를 돌면서 이전 값을 저장해두고 그것을 현재 노드의 next에 대입해준다.

1. 우선 prev의 초기값은 null로 두고 첫번째 노드의 next에 null인 prev를 넣어준다.
2. 그리고 prev는 첫번째 노드로 갱신해 두번째 노드를 돌때 next에 첫번째 노드를 대입해줄 수 있도록 한다.
3. 그리고 현재 값인 curr은 첫번째 노드의 원래 next 값이었던 두번째 노드로 갱신해준다.

위의 과정을 head의 요소들을 돌면서 반복하다 보면 prev에는 next의 참조가 역방향으로 바뀐 ListNode가 들어있게 된다. 따라서 이를 리턴해주면 된다.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if (head == null) return head
        
        var prev: ListNode? = null
        var curr = head
        
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        
        return prev
    }
}