python实现leetcode之92. 反转链表 II

解题思路

步骤：
1.先移动m步
2.然后反转n-m个节点
使用头插法反转链表，连续n次
后续的直接连接在链表尾部
3.一起返回

92. 反转链表 II

代码

# 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, m: int, n: int) -> ListNode:
        if m > 1: # 先移动到m处
            head.next = self.reverseBetween(head.next, m-1, n-1)
            return head
        else:  # 再从m处反转n-m个节点
            tmp = ListNode(0)
            return reverse(head, n, tmp, tmp)


def reverse(li, n, head, tail):
    if n:
        tmp = li.next
        # 头插法反转链表，head指向第一个节点，tail指向最后一个节点
        li.next = head.next
        head.next = li
        if head == tail:
            tail = li
        # 递归处理满n个
        return reverse(tmp, n-1, head, tail)
    else:  # n个已经达到，后面的不用反转
        tail.next = li
        return head.next