# Reverse Linked List II

{% embed url="<https://www.lintcode.com/problem/36/>" %}

{% embed url="<https://leetcode.com/problems/reverse-linked-list-ii/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        // 1. proceed to m's previous node
        for (int i = 0; i < m - 1; i++) {
            if (cur == null) return null;
            cur = cur.next;
        }

        // 2. reverse from m to n
        ListNode mPrev = cur;
        ListNode mNode = cur.next;
        cur = cur.next;
        ListNode prev = null, next;
        for (int i = m; i <= n; i++) {
            if (cur == null) return null;
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 3. connect the lists
        mPrev.next = prev;
        mNode.next = cur;
        return dummy.next;
    }
}
```

### Notes

We have three major steps here:

1. We first proceed to the (m-1)-th node, which is the node before the m-th node. Then we keep track of both of them.
2. We reverse from m to n using the same technique used in the classical [reverse linked list](/algo/linked-list/reverse-linked-list.md).
3. Lastly, do not forget to connect the middle part, i.e., the reversed linked list, with `mPrev` and `cur` pointer.

```java
m = 2, n = 4;

     mPrev      mNode             n
step1: 1------->2------->3------->4------->5------->6

     mPrev      mNode            prev     cur
step2: 1        2<-------3<-------4        5------->6

     mPrev    prev              mNode     cur
step3: 1------->4------->3------->2------->5------->6
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.yushunchen.com/algo/linked-list/reverse-linked-list-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.