LeetCode 92. Reverse Linked List II

파이썬 알고리즘 인터뷰 문제 19번(리트코드 92번) Reverse Linked List II
https://leetcode.com/problems/reverse-linked-list-ii/

나의 풀이

# 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]:
        index = 1
        curr = head
        prev = None
        left_end = None
        right_start = None

        while curr:
            if index == left - 1:
                left_end = curr
            elif index == left:
                middle_end = curr
            if index < left:
                curr = curr.next
            elif left <= index <= right:
                curr.next, curr, prev = prev, curr.next, curr
            elif index == right + 1:
                right_start = curr
                curr = curr.next
            if index > right:
                break
            index += 1
        
        if left_end:
            left_end.next = prev
        else:
            head = prev
        
        middle_end.next = right_start

        return head

다른 풀이

# 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 left == right:
            return head
        dummy = ListNode()
        curr= dummy
        dummy.next = head

        for _ in range(left - 1):
            curr = curr.next
        start = curr
        end = start.next
        nxt = end.next

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

        return dummy.next

배운 점

• 이 문제를 풀 때 가장 까다로운 것은 뒤집어지지 않는 왼쪽 또는 오른쪽 부분이 없을 때이다.
• dummy를 앞에 추가하여 왼쪽 부분 없는 경우를 간단히 처리할 수 있다.
• 나는 prev, curr을 이용했는데 이 경우 오른쪽 부분이 없을 때 처리하기 까다로웠다.
• 책 풀이에서는 end, nxt를 이용했다. 이 경우 오른쪽 부분이 없을 때도 함께 처리된다. 무슨 차이냐면 nxt = start.next.next로 정의되는데 나는 start.next = None인 경우를 염려하여 이렇게 포인터를 두지 못했다.
• 하지만 책 풀이에서는 시작할 때 left = right인 경우를 예외처리를 하여 nxt가 잘 정의되도록 했다.
• 다음으로 왼쪽, 뒤집어진 중간, 오른쪽 부분을 이어주는 것도 책 풀이가 훨씬 좋았다.
• 1->(2<-3<-4)-5 로 연결 된 상태이다. 나는 1, 2에 따로 포인터를 두어 1->4, 2->5를 연결지어 주었다. 그런데 책 풀이에서는 훨씬 똑똑하게 1 포인터만 이용하여 1.next.next = 5(nxt)를 이용하여 2->5를 연결지어주고, 1.next = 4(end)를 이용하여 1->4를 연결지었다.