Zip Linked List

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

using namespace std;

// This is an input struct. Do not edit.
class LinkedList {
public:
  int value;
  LinkedList *next = nullptr;

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

LinkedList* split(LinkedList *head) {
	LinkedList *slow = head, *fast = head, *end = head;
	while(fast and fast->next) {
		end = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	if(fast) {
		end = slow;
		slow = slow->next;
	}
	end->next = nullptr;
	return slow;
}

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

void connect(LinkedList* head1, LinkedList* head2) {
	LinkedList *nxt1 = head1, *nxt2 = head2;
	while(nxt1 and nxt2) {
		nxt1 = head1->next;
		nxt2 = head2->next;
		
		head1->next = head2;
		head2->next = nxt1;
		
		head1 = nxt1;
		head2 = nxt2;
	}
}

LinkedList *zipLinkedList(LinkedList *linkedList) {
	LinkedList* res = linkedList;
	LinkedList* second = split(linkedList);
	LinkedList* reversed = reverse(second);
	connect(linkedList, reversed);
	
  return res;
}