[알고리즘] 역순 연결 리스트 II

역순 연결 리스트 II

책 풀이

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> 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
            start.next = end.next
            end.next = end.next.next
            start.next.next = tmp

        return root.next

리스트에 담아서 필요한 부분만 리버스를 하고 다시 그 리스트를 기반으로 링크드리스트를 만들어도 되겠지만, 그것이 정석 풀이는 아닌듯하여 책의 풀이를 참고 하였다. 어떻게 진행되는지 책의 그림을 통해 이해하는 것이 중요하다.