LeetCode - Reverse Linked List 🤦🏻

 

---

문제

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

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

---

Iteratively - O(N) Time, O(1) Space

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head?.next == nil {
            return head
        }
        var curr : ListNode? = head
        var prev : ListNode? = nil
        var next : ListNode? = nil
        
        while(curr != nil){
            next = curr?.next //next저장
            curr?.next = prev //reverse
            prev = curr       // advance prev 
            curr = next       // advance curr
        }
        return prev // new head at end
    }
}

• prev curr next 포인터 선언
• curr 가 nil 이면 종료
• next 포인터에 curr.next 할당
• curr.next와 prev 을 reverse
• prev 와 curr 앞으로 한단계 진행
• next는 nil 되도 되고 curr은 nil 되었을때 prev 가 reverse된 리스트의 head가 됨
• 그래서 return prev

 

 

Recursively - O(N) Time O(N) Space (b/c stack frame)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        //연결리스트의 항목이 하나라면 reverse 할 필요가 없기 때문에 바로 head 리턴
        guard let node = head , head?.next != nil else {
            return head
        }
        //연결 리스트의 끝부분 까지 내려간다. (끝에 도착하기 전까지 값 없음)
        //초기에는 제일 끝값이 들어가진다.
        //1->2->3->4->5 의 경우 5에 도달할 때 까지 뒤에 코드는 실행안됨
        var reversedListHead : ListNode? = reverseList(node.next)
        //현재노드(1)의 다음노드(2)의 다음노드값(3)을 현재노드로 바꾼다.
        node.next?.next = node
        //현재노드(1)의 다음노드(2)값을 nil로 바꾼다.
        node.next = nil
        
        //본인이 연결리스트의 마지막일 때 본인을 리턴한다.
        return reversedListHead
    }
}

• reversedListHead로 연결리스트의 제일 마지막 노드 참조
• reversedListHead는 연결리스트 마지막 노드 갈 때 까지 return 되지 않음
• head가 head.next를 주며 뒤에 연결 리스트에게 본인을 뺀 reversed된 리스트 물어봄
• 그럼 head.next 같은 방식으로 뒤에 연결 리스트에게 reversed 된 리스트 물어봄
• 이렇게 stack 쌓이다가 base case 가 연결 리스트 한개이기 때문에 본인을 call 한 node 에게 return 된다.
• 5->4->3->2->1 
• 4->3->->2->1
• 3 ->2->1 
• 2->1 
• 1 (base case) node.next == nil
• base case 부터 reversedListHead 쭉쭉 리턴됨
• 1 다음 노드가 없으니 revresedListHead가 2로 리턴되고 2는 본인과 본인을 뺀 완성된 reversed List를 가지고 있는 셈이다.
• 그래서 2는 1의 next 를 즉 node가 2 node.next 가 1 node.next.next(1의 화살표) 를 2로 돌리고
• 2의 next 는 nil로 처리한다. (제일 앞부분일 수 있어서)
• 그리고 reversedHead를 리턴하므로써 3이 이제 나머지 reversed list 인 2<-1 이랑 작업할 수 있게 한다.

 

 

왜 자꾸 Recursion 은 비동기적으로 생각하는 거지

겁나 헷갈린다.