166 - 92 反转链表2

题目

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

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

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

解答

递归

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

继续研究大佬的解法

他的思路是拆解问题。反转链表的一部分=>从头反转到n=>反转全部链表。

反转全部链表，即反转链表1。记录下最后节点之后的节点，即可反转到n。reverseN()。

然后不断递归reverseBetween()，就能得到结果了。

class Solution:

    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        self.successor = None

        def reverseN(head, n):
            if n == 1:
                self.successor = head.next
                return head
            last = reverseN(head.next, n-1)
            head.next.next = head
            head.next = self.successor
            return last
        if m == 1:
            return reverseN(head, n)
        head.next = Solution.reverseBetween(self, head.next, m-1, n-1)
        return head

Runtime: 32 ms, faster than 77.39% of Python3 online submissions for Reverse Linked List II.

Memory Usage: 13.2 MB, less than 33.33% of Python3 online submissions for Reverse Linked List II.

var reverseBetween = function(head, m, n) {
  let successor = null
  const reverseN = function(head, n) {
    if (n === 1) {
      successor = head.next
      return head
    }
    const last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last
  }
  if (m === 1) {
    return reverseN(head, n)
  }
  head.next = reverseBetween(head.next, m - 1, n - 1)
  return head
};

Runtime: 64 ms, faster than 13.75% of JavaScript online submissions for Reverse Linked List II.

Memory Usage: 33.9 MB, less than 42.86% of JavaScript online submissions for Reverse Linked List II.

迭代

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30709/Talk-is-cheap-show-me-the-code-(and-DRAWING)

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head or m == n:
            return head
        p = dummy = ListNode(None)
        dummy.next = head

        for _ in range(m-1):
            p = p.next
        tail = p.next

        for _ in range(n-m):
            tmp = p.next
            p.next = tail.next
            tail.next = tail.next.next
            p.next.next = tmp
        return dummy.next

Runtime: 32 ms, faster than 77.39% of Python3 online submissions for Reverse Linked List II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Reverse Linked List II.

0_1490008790876_reversed_linked_list.jpeg