36.翻转链表(Python)

• 描述
  给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null
• Solution

class Solution:
    """
    @param head: ListNode head is the head of the linked list 
    @param m: An integer
    @param n: An integer
    @return: The head of the reversed ListNode
    """
# 找到k位置的节点
    def findth(self,k,head):
        for i in range(k):
            if head is None:
                return None
            head = head.next
        return head
#三指针单链表翻转
    def reverse(self,head):
        prev = None
        while head!= None:
            next = head.next
            head.next = prev
            prev = head
            head = next
        return head
        
    def reverseBetween(self, head, m, n):
        # write your code here
#创建一个0表头
       dummy = ListNode(0,head)
#找到m位置前一点，用于衔接
       m_prev = self.findth(m-1,dummy)
       m_cur = m_prev.next
#n位置点
       n_cur = self.findth(n,dummy)
#记录n_next，用于衔接
       n_next = n_cur.next
#令n位置点的下一个节点为空，用于单链表翻转
       n_cur.next = None
       self.reverse(m_cur)
#衔接
       m_prev.next = n_cur
       m_cur.next = n_next
       return dummy.next

#dalao做法，翻转数组，再头尾衔接
       if head is None:
            return 
        sub_vals = []
        dummy = ListNode(0,head)
        fake_head = dummy
        i = 0
        while fake_head:
            if i == m-1:
                cur = fake_head.next
                j=i+1
                while j>=m and j<=n:
                    sub_vals.append(cur.val)
                    cur = cur.next
                    j=j+1
                sub_vals.reverse()
                sub_head = ListNode(sub_vals[0])
                sub_dummy = ListNode(0,sub_head)
                for val in sub_vals[1:]:
                    node = ListNode(val)
                    sub_head.next = node
                    sub_head = sub_head.next
                fake_head.next = sub_dummy.next
                sub_head.next = cur
            fake_head = fake_head.next
            i=i+1
        return dummy.next