206. Reverse Linked List

206. Reverse Linked List

 

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

 

 

나도 stack 으로 풀었으나, 제대로 못푼 느낌??

# 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]:
        # 스텍으로 푸는 법
        stack = []
        res = cur = head
        while cur:
            stack.append(cur.val)            
            cur = cur.next
        
        # res = ListNode()
        while stack:
            res.val = stack.pop()
            res = res.next
        return head

 

https://youtu.be/O4po8XPf5Hc?si=1z7qJKMb96WBVXC9

 

 

1. Stack 으로 

 

# 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]:
        # 스텍으로 푸는 법
        stack = []
        cur = head
        while cur:
            stack.append(cur)            
            cur = cur.next
        
        dummy = ListNode(-1)
        cur = dummy
        while stack:
            cur.next = stack.pop()
            cur = cur.next
        cur.next = None

        return dummy.next

 

2. 반복 알고리즘

- p: 이전노드 가리키는 것

- c: 현재 노드 가리치는 것 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None  # 이전 노드를 가리키는 포인터
        curr = head  # 현재 노드를 가리키는 포인터

        while curr:  # 현재 노드가 존재하는 동안 반복
            next_node = curr.next  # 다음 노드를 저장
            curr.next = prev  # 현재 노드의 방향을 뒤집음
            prev = curr  # 이전 노드를 현재 노드로 이동
            curr = next_node  # 현재 노드를 다음 노드로 이동

        return prev  # prev는 뒤집힌 리스트의 새로운 헤드

 

3. 재귀로 

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        new_tail = head.next
        new_head = self.reverseList(head.next)
        new_tail.next = head
        head.next = None
        return new_head

 

최종 코드

 

https://youtu.be/G0_I-ZF0S38

 

# 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]:
        prev, curr = None, head

        # Time O(n), Memory O(1)
        while(curr):
            nxt = curr.next # 현재 다음을 임의로 저장
            curr.next = prev # 화살표 방향 반대
            prev = curr # 원래 방향으로 shift
            curr = nxt  # 원래 방향으로 shift
        return prev

 

좋은 질문이에요! 🙌
이 reverseList 함수는 **단일 연결 리스트(singly-linked list)**를 뒤집는(reverse) 함수예요.
그런데 마지막에 return prev를 하는 이유가 궁금하신 거죠?

---

🔁 리스트 뒤집기의 핵심 흐름:

 

head → 1 → 2 → 3 → 4 → 5 → None

이 리스트를 뒤집으면 이렇게 되어야 해요:

 

None ← 1 ← 2 ← 3 ← 4 ← 5

                                            ↑ prev

---

💡 prev는 새로운 head가 된다!

• curr은 현재 노드를 가리키고,
• prev는 **뒤집힌 리스트의 앞부분(head)**를 계속 저장해가는 변수예요.
• 루프가 끝나면 curr == None이고, prev는 마지막 노드를 가리키게 돼요.
• 근데 뒤집힌 리스트에서는 그 마지막 노드가 새로운 head가 되니까 return prev가 맞는 거예요!

---

🔚 정리하면:

• 원래 리스트의 마지막 노드 → 뒤집힌 리스트의 head
• 그 노드를 prev가 가리키고 있음
• 그래서 return prev!