[LeetCode] 206. Reverse Linked List 역순 연결 리스트

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

206번 Reverse Linked List 는 연결 리스트를 뒤집는 문제이다.

Example

 

 

# 풀이방법 1 - 재귀함수 & Queue 이용(내 풀이)

# 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]:
        
        # reverse 함수에서 노드의 값을 저장하는 큐
        values = deque()
        
        # 재귀함수
        # : 연결 리스트 끝단까지 접근하여 val을 큐에 저장하였다가, 되돌아오면서 큐에 있던 값을 꺼내 값을 변경함
        def reverse(node : ListNode):
            values.append(node.val) # 노드의 val을 큐에 저장
            
            if node.next != None : 
                reverse(node.next) # 재귀 함수 호출
            
            node.val = values.popleft() # 큐에 저장된 값들로 노드의 val 변경
            return node
        
      
        if head != None:
            head = reverse(head)
            
        return head

| 아이디어  | 

큐에 노드의 value를 넣어두고, 재귀로 차례로 연결 리스트의 끝의 노드까지 갔다가, 다시 이전 노드로 돌아오며 큐에 저장되어 있던 값을 꺼내 현재 node의 값을 변경한다.

- reverse 함수  : 재귀 함수로, 연결 리스트 끝단까지 접근하여 val을 큐에 저장하였다가, 되돌아오면서 큐에 있던 값을 꺼내 값을 변경함

 

 

 

# 풀이 방법 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: Optional[ListNode]) -> Optional[ListNode]:
        
        node, prev = head, None
        
        while node :
            # 다음 노드를 저장하고, 현재 노드가 가르키는 포인터 (node.next)가 이전노드(prev)를 가리키도록 한다.
            next, node.next = node.next, prev
            
            # 다음 반복문을 위해 이전 노드인 prev는 현재 노드 node로, 현재 node는 다음노드 next로 지정한다. 
            prev, node = node, next 
        
        return prev

| 흐름 | 

1. 다음 노드를 저장하고, 현재 노드가 가르키는 포인터 (node.next)가 이전노드(prev)를 가리키도록 한다.

2.  다음 반복문을 위해 이전 노드인 prev는 현재 노드 node로, 현재 node는 다음노드 next로 지정한다. 

 

 

| 핵심 |

          # 다음 노드를 저장하고, 현재 노드가 가르키는 포인터 (node.next)가 이전노드(prev)를 가리키도록 한다.
            next, node.next = node.next, prev
            # 다음 반복문을 위해 이전 노드인 prev는 현재 노드 node로, 현재 node는 다음노드 next로 지정한다. 
            prev, node = node, next 

 

 

# 결과