[LEET CODE] 92. Reverse Linked List II

# Problem

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. left, right는 n번째 노드를 뜻함 (1부터 시작) Constraints: The number of nodes in the list is n. 1 <= n <= 500 -500 <= Node.val <= 500 1 <= left <= right <= n

 

# My Answer

# 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: ListNode, left: int, right: int) -> ListNode:
        if head is None or head.next is None or left==right:
            return head
        # a: 리턴할 헤드
        a = node = head
        a_end = a # a_end : 역순 리스트가 아닌 앞부분 (left 앞부분)의 마지막 노드
        rev = head # rev : 역순 리스트
        
        # node를 역순이 시작하는 left 지점으로
        for i in range(left-1):
            node = node.next
            
        # rev는 역순 리스트이고 그 이후에 right보다 뒤에 있는 리스트를 연결해야함
        # rev를 뒤쪽의 리스트로 설정하고 순서를 바꾸면서 앞에 하나씩 연결한다
        for i in range(right):
            rev = rev.next
        
        # 지정한 길이만큼 역순으로 연결
        for i in range(right-left+1):
            rev, rev.next, node = node, rev, node.next
        
        # 앞의 리스트와 역순리스트를 연결하기 위해 앞의 리스트 마지막 노트로 이동
        for i in range(left-2):
            a_end = a_end.next
            
        if left != 1:
            a_end.next = rev
            return a
        else: # left가 1 일 경우(첫 노드부터 역순) 역순 리스트 그대로 반환
            return rev
        

 

# Solution 1 - 반복 구조로 노드 뒤집기

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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 # start : 변경이 필요한 지점의 바로 앞 지점
        end = start.next # 역순 리스트의 마지막

        # 반복하면서 노드 차례대로 뒤집기
        for _ in range(n - m):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            # end가 수정되면서 temp도 수정된다 ( 같은 연결 리스트 참조중)
            start.next.next = tmp
        return root.next