[Leetcode/파이썬] 92. Reverse Linked List II

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?

 

# 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]:
        dummy = ListNode(-501, head)
        curr1 = dummy
        length = right - left + 1

        for _ in range(left) :
            curr1 = curr1.next

        curr2 = curr1

        stack = []

        for _ in range(length) :
            stack.append(curr1.val)
            curr1 = curr1.next

        while stack :
            v = stack.pop()
            curr2.val = v
            curr2 = curr2.next

        return dummy.next

포인터를 잘 쓰자. 그리고 이 문제는 스택의 FILO 특성을 활용하여 풀이할 수 있다. 어떻게 뒤집지? => 스택을 활용하자

처음에 새로운 ListNode를 생성하고 포인터를 2개를 잡을거다. curr1으로 시작. left만큼 넘긴다. [-501, 1, 2, 3, 4, 5] 에서 현재 포인터는 curr1 => 2를 가리킨다. 

이 포인터를 curr2 에 넘겨주고, stack에 curr1.val을 담기 시작한다. stack 에 2, 3, 4 를 순차로 담는다. stack = [2, 3, 4]

현재 스택에 있는 값들을 하나씩 pop 하면서 curr2.val 에 값으로 교체한 후 curr2 포인터를 한칸 뒤로 계속 옮긴다. 이를 스택이 빌 때 까지 반복. [-501, 1, 2, 3, 4, 5] => [-501, 1, 4, 3, 2, 5]

원본인 dummy를 next값으로 반환한다. dummy = [-501, 1, 4, 3, 2, 5]

=> dummy.next = [1, 4, 3, 2, 5]