Reverse Linked List II

Question

Reverse a linked list from position m to n.

Thoughts

这一题规定了reverse的范围，reverse的过程还是可以用1的reverse的方法 关键是找到m-1th node和n+1th node

head不确定，就要用dummy node

• 由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点
• 找到第m个节点, 循环n-m次，使用上题中的list翻转方法
• 处理第m-1个和第n+1个节点
• 返回dummy->next

边界条件：

• m = 1
• n > list长度

Solution

"""
Definition of ListNode

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The head of linked list
    @param m: start position
    @param n: end position
    """
    def reverseBetween(self, head, m, n):
        # write your code here
        if not head:
            return None
        dummy = ListNode(0)
        dummy.next = head
        prev = None
        curr = head
        i = 1
        #findi m-1th node and mth node
        while i < m:
            prev = curr
            curr = curr.next
            i += 1

        nodePreM = prev
        nodeM = curr

        #start reversing from mth node, nth node needs reverse too, so i <= n-m
        i = 0 
        while curr and i <= n-m:
            #print "prev: " + str(prev.val)
            #print "curr: " + str(curr.val)
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
            i += 1

        #reset nodePreM and nodeM links
        #if m == 1, nodePreM doesn't exist
        if m != 1:
            nodePreM.next = prev
        else:
            dummy.next = prev
        nodeM.next = curr

        return dummy.next