[LeetCode] 92. Reverse Linked List II 역순 연결 리스트Ⅱ

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

 

# 문제 설명 

92번 Reverse Linked List II 는 인덱스 m에서 n까지를 역순으로 만드는 문제이다.

Example

 

 

# 풀이방법 1 -  재귀 함수 이용하여 reverse (내 풀이)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        
        # reverse 함수에서 노드의 값을 저장하는 큐
        values = deque()
        
        cnt = 0
        # 재귀함수
        # : 연결 리스트 끝단까지 접근하여 val을 큐에 저장하였다가, 되돌아오면서 큐에 있던 값을 꺼내 값을 변경함
        def reverse(node : ListNode, cnt):
            
            cnt += 1
            
            if cnt >= left and cnt <= right :
                values.append(node.val) # 노드의 val을 큐에 저장
            
            if node.next != None : 
                # print('node : ', node)
                reverse(node.next, cnt) # 재귀 함수 호출
            
            if cnt >= left and cnt <= right :
                node.val = values.popleft() # 큐에 저장된 값들로 노드의 val 변경
                
            return node
    
        if head != None:
            head = reverse(head, cnt)
        
        return head

| 아이디어  | 

206번 Reverse Linked List 풀이를 조금 변형하여 풀었다. 

재귀함수를 돌며, 몇 번째 노드인지 확인을 하다가 인덱스 조건을 만족하면 노드의 값을 큐에 저장하였다가,

다시 돌아오는 재귀 흐름에서 인덱스 조건 만족 시, 큐에서 값을 꺼내어 값을 변경한다.

 

 

 

# 풀이 방법 2 - 반복 구조로 뒤집기 (책 풀이 참고)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        
        # 예외 처리
        if not head or m==n : 
        	return head
           
        root = start = ListNode(None)
        root.next = head 
        
        # start와 end 노드 지정 
        for _ in range(m-1):
        	start = start.next
        end = start.next
        
        
      	# 반복하면서 노드 뒤집기
        for _ in range(n-m) :
        	tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
            
        return root.next

| 아이디어 | 

뒤집어야 하는 노드의 시작과 끝의 노드를 저장한다. 그런다음 for문을 돌며 노드를 차례대로 뒤집는다.

 

 

| 핵심 |

# 반복하면서 노드 뒤집기
        for _ in range(n-m) :
         tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp

 

 

# 결과