# \[92]\[中等]\[递归] 反转链表 II

## 题目描述

[92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

![](/files/-MWHsJKwz3tER93vq1cc)

```
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
```

示例 2：

```
输入：head = [5], left = 1, right = 1
输出：[5]
```

提示：

链表中节点数目为 n

* 1 <= n <= 500
* -500 <= Node.val <= 500
* 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

## 解题思路

与[\[206\]\[简单\]\[递归\]\[双指针\] 反转链表](broken://pages/-MWHs8u1I-uBoj0BYG5g)相似, 只是要首先定位到反转左端起点, 然后用DFS递归的方法从左到右将子链反转, 直到遇到反转子链的右端, 并记录下右端这个节点, 以及后面的节点.

之后的事情就是将反转后的子链与剩余左侧链和剩余右侧链连接.

* 如果反转的左端是1, 反转后的头节点是待反转子链的右端节点

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if left == right:
            return head

        real_head, new_head, new_next = head, None, None
        former, current = None, head
        for _ in range(left - 1):  # 找到left对应的结点
            former = current
            current = current.next

        def dfs(node, count):
            if count == right:
                nonlocal new_head, new_next
                new_head = node
                new_next = node.next
                return node

            new_node = dfs(node.next, count + 1)
            node.next = None
            new_node.next = node

            return node

        new_tail = dfs(current, left)
        if former is None:
            real_head = new_head
        else:
            former.next = new_head
        new_tail.next = new_next

        return real_head
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/lian-biao/92-fan-zhuan-lian-biao-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.