leetcode/python/ 206. Reverse Linked List

Description

Reverse Linked List - LeetCode

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

---

Process

Constraints:

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

처음엔 그냥 반복문을 돌리면서 처리해볼까 했고 그 다음엔 그런데 이거 재귀로 하면 간단하게 할 수 있을 것 같다! 라는 생각을 햇지만......... 내 머리는 아직도 재귀가 버겁다..........

 

---

Solution1: Time: 48 ms (5.42%), Space: 16.2 MB (21.11%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        linked = []
        cur = head
        while cur:
            linked.append(ListNode(val=cur.val))
            cur = cur.next
                
        reversed_nodes = list(reversed(linked))
        
        new_head = reversed_nodes[0]
        new_cur = new_head
        for i in range(1, len(reversed_nodes)):
            new_cur.next = reversed_nodes[i]
            new_cur = new_cur.next        
        
        return new_head

 

맨 처음 직관적으로 작성한 코드다. ListNode를 하나씩 분리해 리스트에 담고, 이후 해당 리스트를 반대로 순회하면서 next를 지정해준다.  

 

---

Solution2: Time: 43 ms (24.50%), Space: 15.3 MB (99.70%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        prev = None
        cur = head
        
        while cur:
            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
            
        return prev

 

1의 약간 업그레이드 버전이다. 반복을 두번 도는 대신 while문 하나로 과정을 처리한다. 

 

1. 현재 노드의 다음 노드를 next_node로 꺼내온다

2. 현재 노드의 next로 prev에 저장된 노드를 연결한다

3. prev에 현재 노드를 저장한다

4. 처음 꺼내왔던 next_node를 다음 반복 노드(cur)로 할당한다

 

먼저 연결되어 있던 node를 임시로 저장해두고, 계속 반대로 연결된 prev node를 연결해주는 것이 핵심이었다.

 

---

Solution3: Time: 40 ms (44.45%), Space: 20.5 MB (5.97%) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

 

* not head -> head = []인 경우 처리

1. head의 next가 없을 때까지 재귀 호출

2. new_head로 마지막 노드를 할당

3. head.next.next = head

• 현재 노드에 연결된 노드가 현재 노드 자신을 바라보게 변경해준다

4. head.next = None

• 현재 노드에 연결된 노드와의 연결을 끊어준다

 

즉 1 -> 2 -> 3 과 같은 링크드 리스트가 있었다면,

재귀 호출을 통해 reverseList(3)에서 not head.next이므로 3을 반환하고, reversedList(2), reversedList(1)이 호출된다.

reverseList(2)에서 new_head로 3이 할당, head.next.next = head에서 2.next == 3이므로, 3.next = 2를 할당한다. 이후 head.next = None에서 원래 연결되어 있던 2->3 으로의 연결 방향을 끊어준다. (1->2<-3)

이후 reverseList(1)에서 동일한 과정을 거쳐 1<-2<-3 방향의 리스트가 완성된다.

 

 

* 재귀 호출 과정 (1->2->3->4->5 인 경우)

---

Conclusion

그나마 base case 잡는 건 조금 익숙해졌는데 탈출 후 연속적인 반환 과정을 코드로 구현하는 게 아직도 많이 어렵다. 일단 복습으로 이겨내자 엉엉