Thursday, June 5, 2014

LeetCode Reverse Linked List II

The key part is "reverse" method.
Also it can be used in the Reverse K group.

public ListNode reverseBetween(ListNode head, int m, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode temp = dummy;
       int i = 1;
       //Find the prev
       while( temp != null && i < m) {
           temp = temp.next;
           i++;
       }
       ListNode prev = temp;
       //Find the next
       while (temp != null && i <= n) {
           temp = temp.next;
           i++;
       }
       ListNode next = temp.next;
       reverse(prev, next);
       return dummy.next;
    }
    private void reverse(ListNode prev, ListNode next) {
        ListNode last = prev.next;
        ListNode curr = last.next;
        while (curr!=next) {
            last.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = last.next;
        }
    }

No comments:

Post a Comment