Leetcode 206. Reverse Linked List with Python - 리뷰 O

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

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

단방향 링크드 리스트의 head가 주어집니다, 이를 거꾸로 돌려서 리턴하세요.

예시

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

제한

• Input: head = []
• Output: []

Python code 관련

본 문제의 Input과 Return은 아래의 형태를 가집니다.

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

풀이법

1. 돌리기

먼저 코드를 보여드리겠습니다.

 class Solution(object):
    def reverseList(self, head):
        hptr = head
        ret = None
        rear = None
        while hptr != None:
            rear = ret
            ret = hptr
            hptr = hptr.next
            ret.next = rear
        return ret
        

hptr을 굳이 따로 빼둔건 이유가 없습니다. 주목하실 부분은 ret과 rear인데요

최종적으로 마지막으로 리턴되는것은 ret이며 rear는 ret의 next가 무엇이 될지를 저장해 놓습니다.

첫 값이 None이기 떄문에 처음 만나는 값의 next는 자연스럽게 None이 될것입니다.

본 과정으로 역순으로 이어줍니다.

위 과정을 간략하게 이미지로 나타내면 다음과 같습니다.

( 2024 / 11 / 23 )

복기

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None

        while cur:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex

        return pre