[LeetCode] #92. Reverse Linked List II (repeat : 0)

Description

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]

---

Solution 

This solution involes in using dummy LinkedList and stores node up to 'left' position. After that, it combines the reversed portion of 'right' into dummy LinkedList. 

 

Code

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        
        if(head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        ListNode prevLeft = null;
        ListNode currentLeft = dummy;
        
        for(int i=0;i<left;i++){
            prevLeft = currentLeft; 
            currentLeft = currentLeft.next;
        } 
        
      
        ListNode prevRight = prevLeft; 
        ListNode currentRight = currentLeft;
        
        for(int i = left; i<= right; i++){
            ListNode forward = currentRight.next; 
            currentRight.next = prevRight;
            prevRight = currentRight;  
            currentRight = forward; 
        }
        
        prevLeft.next = prevRight;
        currentLeft.next = currentRight;
        
        return dummy.next;
        
        
    }
}

 

The reversing of the nodes occures in 'currentRight.next = prevRight'. because the prevRight points to the previous node of the current node.

 

 

Performance 

The time complexity of this algorighm is O(n). Where the n is the number of nodes in the LinkedList. This algorithm uses two for-loops. one is to find the left position and another for-loop reverses nodes between left and right.

The space complexity is O(1) constant space. This algorithm uses only constant amount of variables regardless of the size of the LinkedLIst.