[LinkList]92. Reverse Linked List II

• 分类：LinkList
• 时间复杂度: O(n)
• 空间复杂度: O(n)

92. Reverse Linked List II

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

代码：

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

class Solution:
    def reverseBetween(self, head: 'ListNode', m: 'int', n: 'int') -> 'ListNode':
        
        res=ListNode(0)
        p=res
        
        #第一遍for循环找到m-1的位置，m的位置，n的位置
        current=head
        for i in range(n):
            if i<=m-2:
                p.next=current
                p=p.next
            if i==m-1:
                mNode=current
            if i==n-1:
                nNode=current
            current=current.next
        
        #每次都使prev的next=current，然后current等于当前的prev
        while n-m>0:
            prev=ListNode(mNode.val)
            prev.next=current
            mNode=mNode.next
            current=prev
            m+=1
        mNode.next=current
        p.next=mNode
            
        
        return res.next

讨论：

1.链表题好他妈的眩晕...
2.这是206的一道follow up，这两个题的解法如下：

21881550245660_.pic_hd.jpg