[LeetCode,Python] 92. 역순 연결 리스트 2(Reverse Linked List 2)

인덱스 m에서 n까지를 역순으로 만들어라.

인덱스 m은 1부터 시작한다.

 

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

Output: [1,4,3,2,5]

 

 

 

** 깔끔한 답안 **

 

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 left == right or not head:
            return head
 
        root = start = ListNode(None)
        root.next = head
        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

 

 

해설:

 

역순이 취해지는 지점 바로 전 노드를 first라 하였다.

그리고 역순이 취해지는 노드를 end라 하였다.

단순하게 말하면 ListNode 전체로 봤을 때,

end가 역순이 끝나는 지점까지 나아가면서 자리를 바꿔주도록 하였다.

 

end가 나아가면서 first의 앞 노드와 계속 자리를 바꿔준다.

따라서 first의 앞 노드를 tmp로 두고 진행하였다.

 

손으로 위 코드를 따라 진행해보길 바란다.

 

 

[출처: 파이썬 알고리즘 인터뷰(박상길 지음, 정진호 일러스트) 출판사 : 책만]