Reverse Linked List II(lintcode 36)

Description

Reverse a linked list from position m to n.

Notice:
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Example

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

Interface

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
    }
}

Solution

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
        ListNode prevM = new ListNode(0);
        prevM.next = head;
        for (int i = 0; i < m - 1; ++i) {
            prevM = prevM.next;
        }
        ListNode nodeM = prevM.next;

        ListNode nodeN = head;
        for (int i = 0; i < n - 1; ++i) {
            nodeN = nodeN.next;
        }
        ListNode postN = nodeN.next;
        nodeN.next = null;

        nodeN = reverse(nodeM);
        prevM.next = nodeN;
        nodeM.next = postN;
        if (m == 1) {
            return nodeN;
        } else {
            return head;
        }

    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}