[LeetCode] Reverse Linked List - Python

MinWoo Park·2021년 5월 17일

algorithm

Algorithm

목록 보기

40/42

Algorithm Problem with Python — 40day

문제 설명 📖

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

단일 연결 목록의 헤드가 지정되면 목록을 반대로 적용한 후 반전된 목록을 반환합니다.

입출력 예

Example 1:

nput: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

nput: head = [1,2]
Output: [2,1]

Example 3:

nput: head = []
Output: []

제한사항

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

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

문제 이해 🔑

인풋으로 주어진 연결리스트를 뒤집는 문제입니다.
풀이법으로는 재귀 구조로 뒤집기와 반복 구조로 뒤집기가 되겠습니다.

수도 코드 ✍️

풀이 1. 재귀 구조로 뒤집기

재귀 함수를 만듭니다. 매개변수로는 현재 노드와 이전 노드를 받습니다.
맨 처음 실행할 때 이전 노드가 존재하지 않기에 이전 노드를 받는 매개변수는 기본 매개변수로 만들고 None을 넣습니다.
base case를 작성합니다. 현재 node가 None이라면 이전 노드를 리턴합니다.
recursive case를 작성합니다.
현재 노드의 next 값을 변수에 담습니다.
현재 노드의 next 값에 이전 노드를 재할당 합니다.
다음 노드 next(현재 노드의 next 값)와 현재 노드를 인자로 넣어 재귀 호출을 합니다.

풀이 2. 반복 구조로 뒤집기

현재 노드와 이전 노드를 담을 변수를 만듭니다. 맨 처음 이전 노드는 존재하지 않으니 None을 할당합니다.
반복문을 통해 node가 존재할 때 까지 현재 노드의 next 값을 변수에 담고, 현재 노드의 next 값에는 이전 노드를 재할당 합니다.
반복문이 종료되면 이전 노드를 리턴합니다.

코드 작성 ⌨️

풀이 1. 재귀 구조로 뒤집기

# 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: ListNode) -> ListNode:
        # 함수 정의
        def reverse(node: ListNode, prev: ListNode = 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)

풀이 2. 반복 구조로 뒤집기

# 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: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            # node.next를 이전 prev 리스트로 계속 연결하면서 끝날 때까지 반복
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev