# 92. Reverse Linked List II

### Description

Reverse a linked list from position *m* to *n*. Do it in one-pass.

**Note:** 1 ≤ *m* ≤ *n* ≤ length of list.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/reverse-sublist-linked-list/)
* [Leetcode](https://leetcode.com/problems/reverse-linked-list-ii/)
* [ProgramCreek](https://www.programcreek.com/2014/06/leetcode-reverse-linked-list-ii-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4

**Output:** 1 -> 4 -> 3 -> 2 -> 5 -> NULL
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="ListNode" %}

```java
// Definition for singly-linked list.
public class ListNode {
	int val;
	ListNode next;
	
	ListNode() {}
	
	ListNode(int val) { this.val = val; }
	
	ListNode(int val, ListNode next) { 
		this.val = val; 
		this.next = next;
	}
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N) considering the list consists of N nodes. 
 *    We process each of the nodes at most once (we don't process the nodes 
 *    after the nth node from the beginning).
 * Space complexity : O(1) since we simply adjust some pointers in the 
 *    original linked list and only use O(1) additional memory for achieving 
 *    the final result.
 */

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || m > n) return head;
        ListNode curr = head;
        ListNode first = head, last = null;
        ListNode bfr = null, aft = null;
        
        int i = 1;
        while(i < m) {
            bfr = curr;
            curr = curr.next;
            i++;
        }
        first = curr;

        while(i <= n) {
            ListNode temp = curr.next;
            curr.next = last;
            last = curr;
            curr = temp;
            i++;
        }
        aft = curr;
        
        // Input: head -> .. -> bfr -> reverse(first -> .. -> last) -> aft
        // Output: head -> .. -> bfr -> last -> .. -> first -> aft
        
        if(bfr == null && aft == null) {
            return last;
        }
        
        if(bfr == null) {
            first.next = aft;
            return last;
        }
        
        if(aft == null) {
            bfr.next = last;
            return head;
        }

        bfr.next = last;
        first.next = aft;
        
        return head;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Reverse even elements in a Linked List - [GFG](https://www.geeksforgeeks.org/reverse-even-elements-in-a-linked-list/)