개요

LeetCode #92, Reverse Linked List II 문제를 풀어봅니다.

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

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

Example 2:

Input: head = [5], left = 1, right = 1 Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

left부터 right까지 인덱스 순서 뒤집기를 해야 합니다. start는 변경이 필요한 left의 바로 앞 지점인 left-1을 가리키도록 하고, end는 left를 가리키도록 합니다. root는 head보다 앞에 가 있게 하여 root가 head를 가리키도록 합니다. tmp를 start.next로 지정하고 start.next를 end.next로 만듭니다. end.next는 end.next.next로 지정하고, start.next.next를 tmp로 지정합니다.

# 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:
        # exception
        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
        
        # swap node
        for _ in range(right-left):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
        
        return root.next