86. Partition List

發表於 | 分類於

problem

solution

建立兩個指標分別收集大於等於x的節點與小於x的節點

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *smaller = new ListNode(-1), *a = smaller , *bigger = new ListNode(-1), *b = bigger;
        ListNode *p = head;
        while(p){
            if(p->val >= x){
                b->next = p;
                b=b->next;
            }
            else{
                a->next = p;
                a=a->next;
            }
            p=p->next;
        }
        b->next = nullptr;
        a->next = bigger->next;
        return smaller->next;
    }
};

analysis

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