92. 反转链表 II

https://leetcode-cn.com/problems/reverse-linked-list-ii/

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

通过次数58,417 | 提交次数115,595

Second Try

2020-07-08

递归解法，思路确实独特，很难想到。

理解递归的重点在于，当遇到递归的时候，先假设里面的函数已经处理完毕，然后在这个基础上去处理其他的，最后恰好完成了这个函数本身。按堆栈一路走下去，有时候反而容易绕晕。还有就是直接找到结束点，一点点模拟往上是怎么走的。

这个递归解法，真是见到的特别巧妙的递归了，当然也代表没接触过一下子很难懂。不过自己写一遍，比看官方题解容易理解多了。

参考的题解: @labuladong

https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/bu-bu-chai-jie-ru-he-di-gui-di-fan-zhuan-lian-biao/

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        # 前面的不知道算不是一趟扫描。。

        def fip(head):
            """
            搞个递归反转,这思路太巧妙了
            理解的要点在于把fip函数当作已经翻转成功的来处理
            不过这个基础版没用到，是为了引出接下来的fipn和fipmn版本
            """
            if not head.next:
                return head 
            last = fip(head.next)  # fip后，并没有改变head.next的元素
            head.next.next = head  # 把head元素放在原来的head元素下方的元素后面
            head.next = None  #  既然head已经是末尾了，后面取空值就行了。而且下一波往前推的时候，依然会有新的head放到后面做tail
            return last 
        
        def fipn(head, n):
            """翻转前n个元素, 接下来竟然可以通过递归方法将m,n问题转化为前n问题"""
            if n == 1:
                return head 
            last = fipn(head.next, n - 1)
            downstream = head.next.next 
            head.next.next = head 
            # head.next = None # 后面就不能是None了
            head.next = downstream
            return last 
        
        def fipmn(head, m, n):
            """这些递归的思路真是太巧妙了,很难想到"""
            if m == 1:
                return fipn(head, n)
            head.next = fipmn(head.next, m - 1, n - 1)
            return head 
        
        return fipmn(head, m, n)

执行用时：24 ms, 在所有 Python 提交中击败了54.24%的用户
内存消耗：13.3 MB, 在所有 Python 提交中击败了50.00%的用户

First Try

2020-07-06

在0025做过类似的，一波过了。套路做熟了就还好，比如一些常用的变量写法dummy.next, while node.next， prestart之类，还有倒排翻转之类，链表类的难度比起其他类型真是容易了不少。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        def flip(head, tail):
            start, end = tail, head 
            while head != tail:
                t = tail.next 
                tail.next = head
                head = head.next 
                tail.next.next = t 
            return start, end 
        
        dummy = node = ListNode()
        dummy.next = head 
        c = 0
        prestart = None 
        while node.next:
            c += 1
            if c == m:
                prestart = node 
            elif c == n:
                afterend = node.next.next 
                start, end = flip(prestart.next, node.next)
                prestart.next = start 
                end.next = afterend
                break
            node = node.next 
        return dummy.next 

执行用时：20 ms, 在所有 Python 提交中击败了75.18%的用户
内存消耗：12.6 MB, 在所有 Python 提交中击败了50.00%的用户

92. 反转链表 II​

Second Try​

First Try​

92. 反转链表 II

Second Try

First Try