92. Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed 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]

Constraints:

• The number of nodes in the list is n.

• 1 <= n <= 500

• -500 <= Node.val <= 500

• 1 <= left <= right <= n

My Solution:

Using two pointers l and r to record the boundary of the part that does not participate in the reversal.

Then use three pointers x, y, and z to reverse the middle part, and tmp records the left position of the middle part.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null || left == right){
            return head;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode l = dummy;
        ListNode r = dummy;
        for(int i=1; i<left; i++){
            l = l.next;
        }
        for(int i = 0; i <= right; i++){
            r = r.next;
        }

        ListNode x = l;
        ListNode y = l.next;
        ListNode tmp = y;

        while(y != r){
            ListNode z = y.next;
            y.next = x;
            x = y;
            y = z;
        }

        l.next = x;
        tmp.next = r;

        return dummy.next;
    }
}

Result