Inverted Bisection

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

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

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

int getCountOfNodes(LinkedList* head) {
	LinkedList* tmp = head;
	int count = 0;
	while(tmp) {
		tmp = tmp->next;
		count++;
	}
	return count;
}

LinkedList *getNthNode(LinkedList* head, int n) {
	LinkedList* tmp = head;
	while(--n) {
		tmp = tmp->next;
	}
	return tmp;
}

LinkedList* reverse(LinkedList* head) {
	LinkedList* dummy = new LinkedList(-1);
	dummy->next = head;
	LinkedList* runner = head;
	
	while(runner->next) {
		LinkedList* nxt = runner->next;
		runner->next = nxt->next;
		nxt->next = dummy->next;
		dummy->next = nxt;
	}
	
	return dummy->next;
}

LinkedList *invertedBisection(LinkedList *head) {
  int count = getCountOfNodes(head);
	if(count == 1) return head;
	LinkedList* front = head, *back = nullptr, *middle = nullptr;
	LinkedList* frontTail = getNthNode(head, count / 2);
	
	if(count & 1) {
		back = frontTail->next->next;
		middle = frontTail->next;
	} else { //even
		back = frontTail->next;
	}
	frontTail->next = nullptr;
	LinkedList* reversedFront = reverse(front);
	LinkedList* reversedBack = reverse(back);
	
	if(count & 1) {
		middle->next = reversedBack;
		head->next = middle;
	} else {
		head->next = reversedBack;
	}
	
  return reversedFront;
}