LeetCode 92. Reverse Linked List II

Question

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.

https://leetcode.com/problems/reverse-linked-list-ii/

• Solution1

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode prev = fakeHead;
        ListNode cur = fakeHead.next;
        int i = 1;
        while(i < left){
            prev = cur;
            cur = cur.next;
            i++;
        }
        ListNode node = prev;
        while (i++ <= right){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        node.next.next = cur;
        node.next = prev;
        return fakeHead.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)