# 92. Reverse Linked List II

Reference: LeetCode EPI 7.2
Difficulty: Medium

## Problem

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

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

Example:

## 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.

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.

Reverse helper:

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.

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

Comment
Junhao Wang
a software engineering cat