92. Reverse Linked List II

2019/10/04 Leetcode

Description

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

Solution

// draw a example with 12345
// 100% 100%
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) return head;
        
        ListNode dummy = new ListNode(-1);
        ListNode curr = head;
        dummy.next = curr;
        ListNode prev = dummy;
        int i = 1;
        while (i < m) {
            prev = curr;
            curr = curr.next;
            i++;
        }
        ListNode before = prev;
        ListNode first = curr;
        
        prev = curr;
        curr = curr.next;
        i++;

        while (i <= n) {
            ListNode after = curr.next;
            curr.next = prev;
            prev = curr;
            curr = after;
            i++;
        }
        before.next = prev;
        first.next = curr;
        
        return dummy.next;
        
    }
}

Search

    Table of Contents