92. Reverse Linked List II

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* reverse(ListNode * l, int r){
        ListNode *pre = new ListNode(-1);
        pre->next = l;
        for(int i=0;i<r;++i){
            ListNode *temp = l->next;
            l->next = temp->next;
            temp->next= pre->next;
            pre->next = temp;
        }
        return pre->next;
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left ==1){
            return reverse(head, right-1);
        }
        else{
            head->next = reverseBetween(head->next, left-1, right-1);
        }
        return head;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)