L92. Reverse Linked List II

LinkedList

Problem:

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

• reverse the linked list in a range, in this, reverse 2 -> 3 -> 4

Solution:

• use for loop to find the first node in the range, which is pre

• if pre == null, head is the first node in reverse range

• use for loop to change each node's direction

public ListNode reverseBetween(ListNode head, int m, int n){
    if(head == null || head.next == null) return head;
    ListNode cur = head;
    ListNode pre = null;
    for(int i = 0; i < m -1; i++){
        pre = cur;
        cur = cur.next;
    }
    if(pre != null){
        pre.next = reverseByN(cur, n-m+1);
        return head;
    }else{
        return reverseByN(head, n-m+1);
    }
}
private ListNode reverseByN(ListNode head, int n){
    if(head.next == null) return head;
    ListNode cur = head;
    ListNode pre = null;
    ListNode next = null;
    for(int i = 0; i < n; i++){
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    head.next = next;
    return pre;
}