[Leetcode/Easy] 역순 연결 리스트 (206. Reverse Linked List, Swift)

https://leetcode.com/problems/reverse-linked-list/

 

🤔 문제 설명

연결 리스트를 뒤집어라.

head = [1,2,3,4,5]
// [5,4,3,2,1]

 

💡 풀이 : 연결 리스트 추적하면서 뒤집기

첫 번째 떠오른 방법은 연결 리스트를 처음부터 순차적으로 반복하면서 거꾸로 연결시키는 방법이다.
ListNode의 next에 계속 새로운 값을 추가시키는 것이 아니라, 기존 값을 새로운 next에 계속 할당하는 (= 앞으로 계속 연결하는) 방법을 사용했다고 생각하면 되겠다.

1. 현재 값에 대한 새로운 노드 생성하기 (newNode = ListNode(node.val, rev)) 
2. 새로운 노드 뒤에 기존 노드 연결하기 (rev = newNode)
3. 순서대로 반복해야 하니까 다음 노드로 연결하기 (node = node.next), 해당 노드가 nil이면 반복 종료!

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 6ms (Beats 74.81%), Memory : 15.93MB (Beats 39.10%)

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var headNode: ListNode? = head
        var rev: ListNode? = nil

        while (headNode != nil) {
            let newNode = ListNode(headNode!.val, rev)
            rev = newNode
            headNode = headNode!.next
        }

        return rev
    }
}