/**
* 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | 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; } |