Leetcode92. reverse linked list II

【 secondary 】 Give you the head pointer of the single linked list head And two integers left and right , among left <= right . Please reverse from position left To the position right The linked list node of , return Inverted list .

Example 1：

Input ：head = [1,2,3,4,5], left = 2, right = 4
Output ：[1,4,3,2,5]
Example 2：

Input ：head = [5], left = 1, right = 1
Output ：[5]

Tips ：

The number of nodes in the linked list is n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Solution 1 ：

ListNode m1(ListNode head, int left, int right) {
    
        ListNode virtual = new ListNode(0, head);
        int i = 1;
        ListNode end = head;
        ListNode prev = virtual;
        while (i < right) {
    
            if (i <= left-1) {
    
                prev = prev.next;
            }
            end = end.next;
            i++;
        }
        ListNode last_t = prev;
        ListNode new_t = prev.next;
        ListNode next_h = end.next;
        last_t.next = reverse(prev.next, end);
        new_t.next = next_h;
        return virtual.next;
    }

Solution 2 ：

ListNode m2(ListNode head, int left, int right) {
    
        ListNode v = new ListNode(0, head);
        ListNode curr = head;
        ListNode next = head.next;
        ListNode x = v;
        ListNode s = head;
        ListNode e = head;
        ListNode y = head.next;

        for (int i = 1; i < right; i++) {
    
            if (i == left-1) {
    
                x = curr;
                s = next;
            }
            if (i == right-1) {
    
                e = next;
                y = next.next;
            }

            ListNode next_h = next.next;
            if (i >= left && i <= right-1) {
    
                next.next = curr;
            }
            curr = next;
            next = next_h;
        }

        x.next = e;
        s.next = y;

        return v.next;
    }

ListNode reverse(ListNode start, ListNode end) {
    
        ListNode prev = null;
        ListNode curr = start;
        ListNode stop = end.next;
        while (curr != stop) {
    
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return end;
    }