LeetCode之Reverse Linked List II-python递归解法

太过爱你忘了你带给我的痛 2022-01-14 06:09 71阅读 0赞

题：  
Reverse a linked list from position *m* to *n*. Do it in one-pass.

**Note:** 1 ≤ *m* ≤ *n* ≤ length of list.

**Example:**

Input: 1->2->3->4->5->NULL, m = 2, n = 4
    Output: 1->4->3->2->5->NULL

一般的链表翻转是将整个链表翻转，其图解方法可以参见：[Python剑指offer之反转链表-图解][Python_offer_-]

这道题的一般解法是：首先要添加一个新的头节点，这样可以解决当前头节点发生变动的情况，这是必备套路；然后将3插入到1和2之间，再将4插入到1和3之间。

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> **3** \-> 2 -> 4 -> 5 -> NULL

1 -> **4** \-> 3 -> 2 -> 5 -> NULL

在解释递归解法之前，思考一下对数组的翻转，可以用前后两个指针，向中间移动，同时交换位置

![d1.png][]

链表的递归解法也借用了上面的思路，而且非常巧妙，用了一个trick：用递归来实现链表的回溯，因为链表不像数组，可以从后往前遍历，但借助递归，实际也就是栈，可以实现这一操作，下面为对应的python代码。

class Solution:
        def reverseBetween(self, head, m, n):
            if not head:
                return None
    
            left, right = head, head
            stop = False
            def recurseAndReverse(right, m, n):
                nonlocal left, stop
                if n == 1:
                    return
                right = right.next
                if m > 1:
                    left = left.next
                recurseAndReverse(right, m - 1, n - 1)
                if left == right or right.next == left:
                    stop = True  
                if not stop:
                    left.val, right.val = right.val, left.val
                    left = left.next           
    
            recurseAndReverse(right, m, n)
            return head

代码中的 nonlocal left, stop 非常关键，将 left, stop 设置为了局部的全局变量，这一就可以在recurseAndReverse函数中改变外部变量left, stop的值，而right是recurseAndReverse函数的内部变量，会在递归返回的时候回溯到上一个节点，而left则直接next到下一个节点，实现了和翻转数组一样的操作。

既然翻转链表的升级版可以这么操作，那一般情况就更不在话下了，如下：

def reverse_list(head):
        if not head or not head.next:
            return head
        left, right = head,head
        stop = False
        def recurseAndReverse(right):
            nonlocal left, stop
            if not right: return
            helper(right.next)
            if left == right or right.next == left:
                stop = True
            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next
        recurseAndReverse(right)
        return head

[Python_offer_-]: https://blog.csdn.net/songyunli1111/article/details/79416684
[d1.png]: https://leetcode.com/problems/reverse-linked-list-ii/Figures/92/d1.png