# 92. Reverse Linked List II

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

要reverse指定位置间的`node`，但链表自身没有`index`，只能自己来记录`index`了。

简单的思路是先把当前指针移动m次，到达要reverse的第一个node，然后用 Q206 的方法 reverse 接下来的 m-n 个node，最后再把两头接上。为了应对`m=1`的情况，最左端需要多连一个`node`来保证`left`指针位置有效。

{% content-ref url="206.-reverse-linked-list" %}
[206.-reverse-linked-list](https://xuqiangwen1994.gitbook.io/practice/206.-reverse-linked-list)
{% endcontent-ref %}

或者，用另一种思路去reverse，即遇到第m个`node`后，记录当前`prev[m]`，然后不停地把它后面一个元素放到`prev[m]`的`next`位置，移动`n-m`次，也一样实现 reverse 这一段的效果，且简洁许多，不需要考虑 m, n 取值的 edge case.

{% tabs %}
{% tab title="向前连接reverse" %}

```python
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n: return head
        
        dummy = ListNode(0)
        dummy.next = head
        left = dummy
        for _ in range(m-1): 
            left = left.next
        cur = left.next
        
        right = cur
        for _ in range(n-m+1): 
            right = right.next if right.next else None
        prev = right
        
        for _ in range(n-m):
            follow = cur.next
            cur.next = prev
            prev = cur
            cur = follow
        
        if left: left.next = cur
        cur.next = prev
        
        return dummy.next
```

{% endtab %}

{% tab title="定点插入reverse" %}

```python
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = cur = head
        prev = res
        for _ in range(m-1):
            cur = cur.next
            prev = prev.next
        for _ in range(n-m):
            temp = cur.next
            cur.next = temp.next
            temp.next = prev.next
            prev.next = temp
        return dummy.next
```

{% endtab %}
{% endtabs %}
