main.cpp

/// Source : https://leetcode.com/problems/partition-list/description/
/// Author : liuyubobobo
/// Time   : 2018-07-07

#include <iostream>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/// Linear Scan
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {

        ListNode* dummyHead1 = new ListNode(-1);
        ListNode* dummyHead2 = new ListNode(-1);
        ListNode* prev1 = dummyHead1;
        ListNode* prev2 = dummyHead2;

        for(ListNode* cur = head ; cur != NULL ;){
            if(cur->val < x){
                prev1->next = cur;
                cur = cur->next;
                prev1 = prev1->next;
                prev1->next = NULL;
            }
            else{
                prev2->next = cur;
                cur = cur->next;
                prev2 = prev2->next;
                prev2->next = NULL;
            }
        }

        prev1->next = dummyHead2->next;
        ListNode* ret = dummyHead1->next;

        delete dummyHead1;
        delete dummyHead2;
        return ret;
    }
};


int main() {

    return 0;
}