ID: 36; medium; 翻转链表（二）

## Solution 1 (Java)

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

public class Solution {
/**
* @param m: An integer
* @param n: An integer
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m, int n) {

ListNode dummy = new ListNode(0);
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.

3. Lastly, do not forget to connect the middle part, i.e., the reversed linked list, with `mPrev` and `cur` pointer.

``````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``````

Last updated