> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/lian-biao/92-fan-zhuan-lian-biao-ii.md).

# \[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
```