【数据结构与算法】【LeetCode】【链表】92. 反转链表II

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def createLink_rearinsert(lista):
    head = ListNode(-1)
    rear = head
    for i in lista:
        new_node=ListNode(i)
        rear.next=new_node
        rear=new_node
    return head.next
class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """

        if not head:
            return None

        left, right = head, head
        stop = False
        def recurseAndReverse(right, m, n):
            nonlocal left, stop

            # base case. Don't proceed any further
            if n == 1:
                return

            # Keep moving the right pointer one step forward until (n == 1)
            right = right.next

            # Keep moving left pointer to the right until we reach the proper node
            # from where the reversal is to start.
            if m > 1:
                left = left.next

            # Recurse with m and n reduced.
            recurseAndReverse(right, m - 1, n - 1)

            # In case both the pointers cross each other or become equal, we
            # stop i.e. don't swap data any further. We are done reversing at this
            # point.
            if left == right or right.next == left:
                stop = True

            # Until the boolean stop is false, swap data between the two pointers     
            if not stop:
                left.val, right.val = right.val, left.val

                # Move left one step to the right.
                # The right pointer moves one step back via backtracking.
                left = left.next           

        recurseAndReverse(right, m, n)
        return head
if __name__=="__main__":
    a=[1,4,3,2,5,2]
    new_a=createLink_rearinsert(a)
    a1 = Solution()
    p=a1.reverseBetween(new_a,2,4)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def createLink_rearinsert(lista):
    head = ListNode(-1)
    rear = head
    for i in lista:
        new_node=ListNode(i)
        rear.next=new_node
        rear=new_node
    return head.next
class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """

        # Empty list
        if not head:
            return None

        # Move the two pointers until they reach the proper starting point
        # in the list.
        cur, prev = head, None
        while m > 1:
            prev = cur
            cur = cur.next
            m, n = m - 1, n - 1

        # The two pointers that will fix the final connections.
        tail, con = cur, prev

        # Iteratively reverse the nodes until n becomes 0.
        while n:
            third = cur.next
            cur.next = prev
            prev = cur
            cur = third
            n -= 1

        # Adjust the final connections as explained in the algorithm
        if con:
            con.next = prev
        else:
            head = prev
        tail.next = cur
        return head

if __name__=="__main__":
    a=[1,4,3,2,5,2]
    new_a=createLink_rearinsert(a)
    a1 = Solution()
    p=a1.reverseBetween(new_a,2,4)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)