Linked List Palindrome

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

using namespace std;

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

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

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

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

bool verify(LinkedList* head1, LinkedList* head2) {
	while(head1 and head2) {
		if(head1->value != head2->value) return false;
		head1 = head1->next;
		head2 = head2->next;
	}
	return true;
}

bool linkedListPalindrome(LinkedList *head) {
  LinkedList* second = split(head);
	LinkedList* reversed = reverse(second);
	
  return verify(head, reversed);
}