/**
* 92. Reverse Linked List II
* Reverse a linked list from position m to n. Do it in one-pass.
* Note: 1 ≤ m ≤ n ≤ length of list.
*
* Example:
*
* Input: 1->2->3->4->5->NULL, m = 2, n = 4
* Output: 1->4->3->2->5->NULL
*/
See solution to the question on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ReverseLinkedListTwo.java
Observation: The question is similar to reverse a linked list except that we need to handle some edge cases where we are reversing elements between a start and end index and not the whole linked list. This can be solved via first advancing the pointers in the linked list m times. Then adding the next n characters to a stack and then popping elements off of stack while connecting prior to next element. An edge case arises where if m starts from first element we need to handle the case where head will get replaced by the element at the nth index.
Here is the code:
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head.next == null) return head;
m--; //the index of first element is 1 , hence decrement as we are starting first from 0
int i =0;
//progress the pointers forward
ListNode origHead = head;
ListNode priorEnd = null;
for (; i < m && head != null; i++) {
priorEnd = head;
head = head.next;
}
int noToReverse = n-m;
//add to stack the number of elements needed to be reversed
Stack<ListNode> stack = new Stack<>();
for (i=0; i < noToReverse && head != null; i++) {
stack.add(head);
head = head.next;
}
//keep track of what was next
ListNode next = head;
//adjust pointers by popping last from stack
while (!stack.isEmpty()) {
ListNode node = stack.pop();
if (priorEnd == null) {
origHead = node; //if you starting from the first element in the list priorEnd is null
} else {
priorEnd.next = node;
}
priorEnd = node;
}
//adjust prior end to next
if (priorEnd != null) {
priorEnd.next = next;
}
return origHead;
}