[leetcode] 92. 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(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        if not head or left == right: 
            return head 
        
        root = start = ListNode(None)
        root.next = head 
        # start, end 지정 
        for _ in range(left - 1): 
            start = start.next 
        end = start.next 
            
        # 반복하면서 뒤집기 
        for _ in range(right - left): # 2번 
            tmp = start.next 
            start.next = end.next 
            end.next = end.next.next 
            start.next.next = tmp
            
        return root.next