[leetcode / 206] Reverse Linked List

in Problem Solving on leetcode


날짜: 2021년 8월 25일
카테고리: 연결 리스트
태그: Easy, 206, 파이썬

leetcode 206 - Reverse Linked List

입출력 예시

예제 입력예제 출력
head = [1,2,3,4,5][5,4,3,2,1]
head = [1,2][2,1]
head = [][]

코드

# 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 = None
        
        while head:
            curr= head
            head = head.next
            curr.next = prev
            prev = curr
            
        return prev
파이썬 알고리즘 인터뷰 8-3

풀이 과정


출처 : https://www.geeksforgeeks.org/reverse-a-linked-list/
위의 코드 로직을 그림으로 표현


가장 먼저 prev에 None을 저장

  • 현재 노드를 가리키는 역할을 하는 curr에 head정보를 저장하고
  • head에는 다음에 올 노드 정보를 저장 (원래의 순서대로)
  • curr의 다음에 올 노드 정보에 prev를 넣어 역순으로 방향을 변환
  • prev에는 현재 curr의 정보를 저장

위의 절차를 head가 None이 될 때까지 반복하여 포인터의 방향이 역순으로 변환 된 연결 리스트 prev를 반환

반성

  • 연결 리스트에 대해 완전히 이해하고 있다고 생각했는데, 막상 연결리스트를 활용한 알고리즘 문제를 풀어보니 이해도가 낮아 버벅임이 있었다. 모든 이론적인 부분에 대한 이해만 하고 있는 상황에서 완전하게 내 것으로 만들 필요가 있다.


© 2021. by hminkim