[1] 206. Reverse Linked List

[robert-min]

문제 추천 이유!!

• Linked list 문제
  • 풀 때마다, 원하는 값의 형태로 나오지 않음(테스트 프로그램에 따라 input값의 형태가 조금씩 차이가 있기 때문에 어떻게 원하는 next가 나오는지 빠르게 파악하는게 중요)

문제 링크

https://leetcode.com/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=leetcode-75

*작성가이드 입니다.

1. 작성자가 먼저 문제를 풀어봅니다.
2. 문제를 풀고나서 난이도를 설정합니다.

• 1 : 30분 이내로 손 쉽게 풀 수 있음
• 2 : 1시간 이내로 고민하면 풀 수 있음
• 3 : 1시간 이상 걸리거나 어려움

3. Coding test Basic template을 사용하여 이슈를 생성합니다.

• 제목은 : [난이도] 문제명으로 작성합니다.
• 내용은 : 문제 링크만 추가하세요
• 문제 사이트를 label로 추가해주세요. 기본값은 백준

4. 문제 풀이는 이슈의 코멘트로 추가해주세요

• 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
• 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!

5. 다른 사람에게 채팅으로 직접 문제를 추천하세요.

• 디스코드 채널을 통해 다른 모임원에게 문제를 추천
• 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : 15분
🗂️ 유형 : Linked list

🖌️ 문제 풀이

• 파이썬 인스턴스 변수를 어떻게 빠르게 접근할 것인지 파악하는 것이 중요

• 재귀 풀이

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def reverse(node, prev = None):
            
            # base case
            if not node:
                return prev
            
            # recursive case         
            # next 변수에 현재 노드의 next를 넣고 매개변수 node로 재귀 호출, node.next에는 이전 호출의 노드를 재할당
            next, node.next = node.next, prev
            # next가 재귀 호출 시 매개변수 node 자리로 들어감, 현재 node는 prev 자리로 들어감
            return reverse(next, node) 
        
        # 함수 실행
        return reverse(head)

• 반복구조 풀이

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            # node.next를 이전 prev 리스트로 계속 연결하면서 끝날 때까지 반복
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev