92. Reverse Linked List II

이 문제는 책에 나와 있는 풀이는 어려운편인것 같다. (내 이해도가 문제인가)

 

Linked List문제는 손으로 그려보면 답은 보인다. 

이 문제 역시 책으로 이해하려고 해보다가 손으로 그려서 해결한 문제이다.

 

특정 범위가 주어지고, 그 범위 안에 있는 Linked List를 뒤집는 문제이다. 

 

1) Reverse 후에 앞, 뒤 연결은 어떻게 할것인가?

2) Reverse는 어떤 방법으로 할것인가?

 

2번 질문부터 답해보자, 

-> 나는 head앞에 prev라는 Linked List를 두고 기억하게 했다. 

1번에 대해서는 cnt라는 변수를 두어, 세어 나가면서 m과 같을때 prev.next 를 reverse된 Linked List와 연결 시켰다. 

 

code는 더러운 편이다

    def reversebetween(self, head:ListNode, m:int, n:int) -> ListNode:
    	# 뒤집기 함수
        def getReverse(h:ListNode, c:int)->ListNode:
            node, prev = h, None
            # c1은 뒤집기를 위해서 사용하고, c2는 추후 마지막을 연결하기 위해서 사용
            c1 = c
            c2 = c
            # 2->3->4에서 4의 연결부를 기억하기 위해서 사용
            tail = ListNode(None)
            
            while c1 >= 0:
            	# 마지막이면 연결부를 기억하자
                if c1 == 0:
                    tail = node.next

				# 뒤집기...next라는 임시 변수를 통해서 뒤집자
                next, node.next = node.next, prev
                prev, node = node, next
                c1 -= 1


			# 맨 마지막을 연결시켜주기 위해서 사용
            p1 = prev
            while c2 >= 0:
                if c2 == 0:
                    p1.next = tail
                p1 = p1.next
                c2 -= 1
            return prev

		# head보다 앞선 것을 하나 두고, 이전 값을 기억하자.
        root = prev = ListNode(None)
        prev.next = head
        root.next = head
        cnt = 1
        
        while head:
            if cnt == m:
                prev.next = getReverse(head, n-m)
                break
            cnt += 1
            prev = prev.next
            head = head.next
        return root.next