Shift 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;
  }
};

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

LinkedList *shiftLinkedList(LinkedList *head, int k) {
	int sz = size(head);
	if(k < 0) {
		k = ((k / sz) - 1) * -sz + k;
	}
	k = k % sz;
	if(k == 0) return head;
	
	LinkedList* faster = head;
	for(int i = 0; i < k; i++)
		faster = faster->next;
	
	LinkedList* oldHead = head;
	
	while(faster->next != nullptr) {
		faster = faster->next;
		oldHead = oldHead->next;
	}
	faster->next = head;
	head = oldHead->next;
	oldHead->next = nullptr;
	return head;
}