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

题目描述

92. 反转链表 II

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

示例 1：

输入：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][简单][递归][双指针] 反转链表相似, 只是要首先定位到反转左端起点, 然后用DFS递归的方法从左到右将子链反转, 直到遇到反转子链的右端, 并记录下右端这个节点, 以及后面的节点.

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

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

# 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