leetcode-algorithms/src/ReverseLinkedListII.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// T: O(n)
// S: O(1)

public class ReverseLinkedListII {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;

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

        ListNode temp = start;
        int i = 1;
        for ( ; i < left ; i++) {
            temp = temp.next;
        }

        ListNode a = temp.next, b = temp.next.next, c = temp.next.next.next;
        a.next = null;

        for ( ; i < right && c != null; i++) {
            b.next = a;
            a = b;
            b = c;
            c = c.next;
        }
        if (i < right) {
            b.next = a;
            if (left != 1) {
                temp.next = b;
                return start.next;
            }
            return b;
        }
        temp.next.next = b;
        temp.next = a;
        return start.next;
    }
}