LeetCode 92(Reverse Linked List II, Python)

1. 문제 링크

• https://leetcode.com/problems/reverse-linked-list-ii/

Reverse Linked List II - LeetCode

2. 문제 설명

• 주어진 연결 리스트에서 특정 범위의 노드들을 역순으로 바꾸는 문제
• 예시) head = [1,2,3,4,5], left = 2, right = 4이 주어지면 [1,4,3,2,5]를 반환

3. 처음 풀이

• 통채로 역순시키는 문제(206번)이 있었다.
• 주어진 left, right 기준 바깥 경계를 미리 start, end로 지정해둔다.
• 그리고 역순시켜야하는 구간에서 206번 풀었던 방법으로 역순을 시킨 후 start, end에 연결시킨다.
• 마지막에 head를 반환하면 되는데 이때 left=1인 경우는 head가 아닌 prev 반환

# 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 not head.next:
            return head
        
        # 예외 처리: 노드가 두 개일 때
        if not head.next.next:
            # left와 right가 같으면 변화 없이 그대로 반환
            if left == right:
                return head
            # left와 right가 다르면 두 노드의 순서를 바꿔서 반환
            else:
                nxt = head.next
                nxt.next = head
                head.next = None
                return nxt

        # 새로운 노드를 시작점으로 설정하고 head를 연결
        start = ListNode()
        start.next = head
        idx = 0

        # 시작점까지 이동
        while idx < left - 1:
            start = start.next
            idx += 1
        
        # 끝점을 시작점으로 설정
        end = start

        # 끝점을 right + 1까지 이동
        while idx < right + 1:
            end = end.next
            idx += 1

        # 역순으로 만들기 위해 필요한 변수들 설정
        cur = start.next
        prev = end

        # 역순으로 노드 연
        while cur != end:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        # 시작점과 끝점 연결
        start.next = prev

        # 만약 left가 1이 아니면 원래 head 반환, left가 1이면 역순으로 변환된 리스트의 첫 번째 노드 반환
        return head if left != 1 else prev

4. 다른 풀이

two pointer 풀이

• 123/4567/89에서 4567을 역순으로 바꿔야한다면 5, 6, 7을 순서대로 앞으로 하나씩 옮겨서
• 4567→5467→6547→7654로 바꾸는 풀이

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        """
        123 / 4567 / 89 라 하고 4567을 역순으로 한다고 하자
        """
        if not head or m == n: return head
        p = dummy = ListNode(None)
        dummy.next = head
        for i in range(m-1): p = p.next
        tail = p.next

        """
        여기까지 포인터 위치를 나타내면 아래와 같다. 
        N 123 / 4567 / 89
        d h p / t

        """

        for i in range(n-m):
            tmp = p.next
            p.next = tail.next
            tail.next = tail.next.next
            p.next.next = tmp
        
        """
        for문 1번 돌면(m: tmp) 5를 앞으로 가져옴
        N 123 / 5467 / 89
        d h p /  t
        d h p /  m

        for문 2번 돌면 6을 앞으로 가져옴
        N 123 / 6547 / 89
        d h p /  mt

        for문 3번 돌면 7을 앞으로 가져오고 완료
        N 123 / 7654 / 89
        d h p /  m t
        """

        return dummy.next

---

recursion 풀이

• left까지 이동하는게 재귀로 처리되고, left부터 right까지 순서 바꾸는건 while 반복문으로 위와 같은 방식으로 처리됨.
• recursion에 추가 메모리가 필요하므로 two pointer 풀이가 더 좋다고 생각함.

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not (head and left < right):
            return head

        def helper(node, m):
            nonlocal left, right
            if m == left:
                prev = None
                current = node
                while m <= right:
                    current.next, prev, current = prev, current, current.next
                    m += 1
                node.next = current
                return prev
            elif m < left:
                node.next = helper(node.next, m + 1)
            return node

        return helper(head, 1)

---

stack 풀이

• left부터 right까지 노드를 저장해두었다가 역순으로 꺼내면서 연결한다.
• 로직이 간단하지만 two pointer보다 공간 복잡도가 높다. (O(1) vs O(n)) 마찬가지로 two pointer 풀이가 더 좋다고 생각.

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        for _ in range(left - 1):
            prev = prev.next

        stack = []
        current = prev.next

        for _ in range(right - left + 1):
            stack.append(current)
            current = current.next

        while stack:
            prev.next = stack.pop()
            prev = prev.next

        prev.next = current

        return dummy.next

5. 배운 점

• 제일 앞이나 뒤에 더미 추가하면 편한 경우가 많다.
• 무작정 tmp 노드 안 만들고 풀려고 했는데 그러면 케이스를 나누어 반환하게 되었음. tmp 노드를 만드는 편이 더 나을 때가 있다.