# 92. Reverse Linked List II

Reference: LeetCode EPI 7.2

Difficulty: Medium

My Post: 0 ms Java Solution (Iteration & Recursion) Idx is important!

## Problem

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

**Note:** `1 ≤ m ≤ n ≤ length`

of list.

**Example:**

1 | Input: 1->2->3->4->5->NULL, m = 2, n = 4 |

## Analysis

**Focus on One-Pass Iteration!**

### One-Pass Iteration

- The drawback of the above approach is that it requires two passes over the sublist.
- Once we reach the m-th node, we start the reversing process and keep counting.
- Once we reach the n-th node, we stop the reversion process and link the reversed section with the unreversed sections.

1 | // 2 4 |

**Time:** $O(N)$**Space:** $O(1)$

### Two-Pass Iteration

We can treat this problem as a pure list reversal problem, but we need to locate the m-th node and n-th node.

- Get the list between $m$ and $n$.
- Reverse the list.
- Concatenate the list with the list before $m$ and the list after $n$.

**Note:**

- Using a
`count`

variable brings about clean code. - Use a dummy node to get rid of null check.
- Use two pointers
`p`

and`prev`

. After reversal, we need to update the next pointer of (m-1)-th node.

1 | // Iteration |

Reverse helper:

1 | // pure reverse |

**Time:** $O(N)$**Space:** $O(1)$

### Recursion

Write a recursive function that does not really reverse the list, but locate the nodes $m$ and $n$.

Use a pure reverse function to reverse the list.

Here is the helper function.

1 | private ListNode reverseAmong(ListNode x, int m, int n, int count) { |

**Time:** $O(N)$**Space:** $O(N)$ in the worst case when we have to reverse the entire list.

Comment