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.
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode] #169. Majority Element (repeat : 0 ) (0) | 2024.01.21 |
---|---|
[LeetCode] #234 Palidrome LinkedList (repeat : 1) (0) | 2024.01.19 |
[LeetCode] #26. Remove Duplicates from Sorted Array (reapeat : 0) (0) | 2024.01.17 |
[LeetCode] #27. Remove Element (repeat : 0) (0) | 2024.01.16 |
[LeetCode] #88. Merge Sorted Array (repeat : 0) (0) | 2024.01.16 |