[LeetCode 75] Easy - 206. Reverse Linked List

206. Reverse Linked List

 

나도 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