LeetCode 92. Reverse Linked List II

Description

https://leetcode.com/problems/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?

Explanation

First, find out the node values need to be reversed and the positions where the reverse begins. Then build a reversed node list. Thirdly, combine the reversed node list with the original node list.

Python Solution

# 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:
        
        i = 1
        
        in_range_node_values = []
        
        dummy = ListNode(0)
        dummy.next = head
        

        prev_left = dummy
        after_right = None
             
        while head:
            if i == left - 1:
                prev_left = head
            elif i == right + 1:
                after_right = head
            elif i >= left and i <= right:
                in_range_node_values.append(head.val)    
            
            prev = head           
            head = head.next
            
            i += 1
        
        in_range_node_values = in_range_node_values[::-1]    
        reversed_in_range_node_list = self.get_node_list(in_range_node_values)
        
        prev_left.next = reversed_in_range_node_list
           
        head = dummy.next
        
        while head.next:
            head = head.next
            
        head.next = after_right
                
        return dummy.next
        
        
    def get_node_list(self, values):        

        dummy = ListNode(0)
        prev = dummy
                
        for value in values:
            node = ListNode(value)            
            prev.next = node
            prev = node
                    
        return dummy.next       
        
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.