Rearrange Linked List

• Time : O(n)
• Space : O(1)

using namespace std;

class LinkedList {
public:
  int value;
  LinkedList *next;

  LinkedList(int value) {
    this->value = value;
    next = nullptr;
  }
};

LinkedList *rearrangeLinkedList(LinkedList *head, int k) {
  LinkedList *smallerDummy = new LinkedList(-1), *smallerTail = smallerDummy;
	LinkedList *biggerDummy = new LinkedList(-1), *biggerTail = biggerDummy;
	LinkedList *kDummy = new LinkedList(-1), *kTail = kDummy;
	
	while(head) {
		LinkedList* nxt = head->next;
		head->next = nullptr;
		if(head->value < k) {
			smallerTail->next = head;
			smallerTail = smallerTail->next;
		} else if(head->value == k) {
			kTail->next = head;
			kTail = kTail->next;
		} else {
			biggerTail->next = head;
			biggerTail = biggerTail->next;
		}
		head = nxt;
	}
	
	LinkedList* tail = smallerTail;
	if(kDummy != kTail) {
		tail->next = kDummy->next;
		tail = kTail;
	}
	if(biggerDummy != biggerTail) {
		tail->next = biggerDummy->next;
	}
	
  return smallerDummy->next;
}