92. Reverse Linked List II

92. Reverse Linked List II

 

GPT 코드

# 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]:
        # Step 1: Dummy 노드 생성 (head가 바뀌는 경우를 처리하기 위해)
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # Step 2: left 노드 이전까지 이동
        for _ in range(left - 1):
            prev = prev.next

        # Step 3: left부터 right까지 노드 뒤집기
        reverse_start = prev.next
        current = reverse_start.next

        for _ in range(right - left):
            reverse_start.next = current.next
            current.next = prev.next
            prev.next = current
            current = reverse_start.next

        # Step 4: 변경된 리스트 반환
        return dummy.next

 

 

https://youtu.be/RF_M9tX4Eag?si=ZtQuCdBsnW_wbw7V

 

dummy = ListNode(val=0, next=head) # 값은 0, next 포인터는 head 를 가리키게.

# 1) reach node at position "left"

leftPrev, cur = dummy, head

 

for i in range(left-1):

    leftPrev, cur = dummy, head # 여기서는 prev 대신에 leftPrev 로 이름

 

 

# Now, cur="left", leftPrev="node before left"

# 2) reverse from left to right

prev = None

for i in range(right-left+1):

    tmpNext = cur.next

    cur.next = prev

    prev = cur

    cur = tmpNext

 

# Updated pointers

leftPrev.next.next = cur # cur is node after "right"

leftPrev.next = prev # prev is right

return dummy.next

 

# 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]:
        # 더미 노드 생성
        # 더미 노드는 리스트의 head가 변경될 가능성을 처리하기 위해 사용
        dummy = ListNode(val=0, next=head)  # 값은 0, next는 head를 가리킴

        # 1) "left" 위치까지 이동
        # left 이전 노드를 가리키는 포인터(leftPrev)와 현재 노드(cur)를 초기화
        leftPrev, cur = dummy, head  # leftPrev는 더미 노드를, cur는 head를 가리킴
        for i in range(left - 1):  # left 이전까지 이동
            leftPrev, cur = cur, cur.next  # leftPrev는 현재 노드로, cur는 다음 노드로 이동

        # 반복문 종료 시:
        # - cur: left 위치의 노드를 가리킴
        # - leftPrev: left 이전 노드를 가리킴

        # 2) left부터 right까지의 노드 뒤집기
        prev = None  # 이전 노드를 가리키는 포인터 초기화 (None)
        for i in range(right - left + 1):  # 뒤집기 작업을 right - left + 1번 수행
            tmpNext = cur.next  # 현재 노드의 다음 노드를 임시 저장
            cur.next = prev  # 현재 노드의 next를 이전 노드(prev)로 변경 (역방향 연결)
            prev = cur  # 이전 노드를 현재 노드로 업데이트
            cur = tmpNext  # 현재 노드를 다음 노드로 업데이트

        # 반복문 종료 시:
        # - prev: 뒤집어진 구간의 첫 번째 노드를 가리킴 (원래는 right 노드)
        # - cur: 뒤집어진 구간의 다음 노드를 가리킴 (원래는 right 이후의 노드)
        """
        이 반복문이 끝나면:
        prev는 4 (→ 3 → 2)를 가리킴 (뒤집어진 구간).
        cur은 5를 가리킴 (right 이후의 첫 번째 노드).
        """

        # 3) 포인터 업데이트
        # leftPrev.next: 뒤집어진 리스트의 첫 번째 노드(prev)를 가리키도록 설정
        leftPrev.next = prev   # leftPrev의 next가 뒤집어진 첫 번째 노드(4)를 가리킴
        # leftPrev.next.next: 뒤집어진 리스트의 마지막 노드가 뒤집어진 구간 이후 노드(cur)를 가리키도록 설정
        leftPrev.next.next = cur   # 뒤집어진 마지막 노드(2)가 right 이후의 노드(5)를 가리킴

        """
        뒤집기 작업만으로 노드의 링크가 역순으로 연결됩니다.
        하지만 leftPrev.next.next = cur은 
            뒤집힌 구간의 마지막 노드를 cur(right 이후의 노드)와 
            명시적으로 연결하기 위해 **꼭** 필요합니다.
        이 작업이 없으면 리스트의 구조가 완전히 연결되지 않습니다.
        """

        # 더미 노드의 next 반환 (실제 리스트의 헤드)
        return dummy.next