19. Reverse Linked List II

아현·2021년 3월 23일
0

Algorithm

목록 보기
20/400
post-custom-banner

리트코드

  • 인덱스 m(left)에서 n(right)까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

  • left, right가 left <= right일 때 left와 right를 역순으로 만들어라 그리고 역순 리스트를 리턴하라



1. 반복 구조로 노드 뒤집기



# 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: ListNode, left: int, right: int) -> ListNode:
        
        #예외처리
        if not head or left == right:
            return head
        
        root = start = ListNode(None)
        root.next = head
        
        #start, end 지정
        
        for _ in range(left - 1):
            start = start.next
        
        end = start.next
        
        #반복하면서 노드 차례대로 뒤집기
        
        for _ in range(right - left):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
            
        return root.next



  • left는 2, right는 5로 가정하고 풀이를 진행해보자

  • start는 변경이 필요한 2의 바로 앞 지점인 1을 가리키게하고, end는 start.next인 2로 지정한다.

  • head는 1인테, 그보다도 더 앞에 root를 만들어 head보다 이전에 위치시킨다.

    • 나중에 root.next를 최종 결과로 리턴하게 된다.
  • start와 end를 기준으로 다음과 같이 반복하면서 역순으로 뒤집는다.


  • 2) 부터가 반복하며 진행되는 부분이다.

  • start.next를 tmp로 지정하고, start.next는 end.next가 된다.

  • end.next는 end.next.next로 한 칸 더 앞의 값을 끌어온다. 그리고 start.next.next를 tmp로 지정한다.

    • 즉, 이전에 start.next였던 노드를 배치하는 것과 동일하다.
  • right - left 만큼 반복하면 최종 결과는 5)번 결과가 된다.

  • 마지막으로 root.next를 리턴하면 된다.


  • 다중할당

    • 다음과 같이 풀어서도 동일한 결과를 얻을 수 있다.

   for _ in range(right - left):
   	tmp = start.next
    start.next = end.next
    end.next = end.next.next
    start.next.next = tmp



✔ 언더스코어 ( _ )

  1. 인터프리터에서 마지막 값을 저장할 때

  2. 값을 무시하고 싶을 때

  3. 변수, 함수 명에 특별한 의미 또는 기능을 부여할 때

  4. 국제화, 지역화 함수로써 사용할 때

  5. 숫자 리터럴 값의 자릿수 구분을 위한 구분자로 사용할 때

profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글