Reverse Linked List II

Reverse a linked list from position m to n.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Solution

ReverseNextK

http://www.lintcode.com/problem/reverse-nodes-in-k-group/

"""
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):
        if m >= n and head == None:
            return head
        dummyNode = ListNode(0)
        dummyNode.next= head
        head = dummyNode

        for i in range(1, m):
            head = head.next

        first = head
        prev = None
        head = head.next
        tail = head.next
        for i in range(m, n + 1):
            tmp = head.next
            head.next = prev
            prev = head.next
            head = tmp

        tail.next = head
        first.next = prev

        return dummyNode.next