#include <cstdlib> // To allow NULL if no other includes
#include <iostream>
using namespace std;


struct Node {
	Node(int data = 0, Node* link = NULL) : data(data), link(link) {}
	int data;
	Node* link;
};

void listInsertHead(int entry, Node*& headPtr) {
	headPtr = new Node(entry, headPtr);
}


void splice(Node* headptr2, Node* target) {
	//target is a pointer to 7 Node
	Node *temp = target->link; //store a temporary pointer for the target's pointer
	target->link = headptr2; //change the target pointer to L2's first Node
	while (headptr2->link != nullptr) //while there is a next pointer after current,
		headptr2 = headptr2->link; //current gets next pointer
	if (headptr2 != nullptr) //if L2 is not empty,
		headptr2->link = temp; //the pointer to the last element of L2 gets the temporary pointer stored from earlier
}


Node* isSubList(Node*headptr1, Node* headptr2) {
	while (headptr1->data != headptr2->data) { //data in L1 doesn't match data in L2,
		headptr1 = headptr1->link; // increment headptr1 until the data does match
	}
	Node *temp = headptr1;
	bool isSubList = true;
	while (isSubList && (headptr2->link != nullptr)) { //while the data matches, increment both pointers
		headptr1 = headptr1->link;
		headptr2 = headptr2->link;
		if (headptr1->data == headptr2->data)
			isSubList = true;
		else
			isSubList = false;
	}

	if (isSubList)
		return temp;
	else {
		cout << "Failed to match" << endl;
		return nullptr;
	}
}


void printList(Node* head) {
	//if (head == nullptr) { cout << "nullptr"; }
	while (head != nullptr) { //while temp->link != nullptr is not the right code
		cout << head->data << " ";
		head = head->link;
	}
	cout << endl;
}


int main() {
	Node *head1 = nullptr; //head1 points to the first Node of L1
	listInsertHead(1, head1);
	listInsertHead(9, head1);
	listInsertHead(7, head1);
	listInsertHead(5, head1); // 5 7 9 1

	Node *head2 = nullptr; //head2 points to the first Node of L2
	listInsertHead(2, head2);
	listInsertHead(3, head2);
	listInsertHead(6, head2); //6 3 2

	cout << "Part One:" << endl << endl;
	cout << "L1: ";
	printList(head1);
	cout << "L2: ";
	printList(head2);
	Node *target = head1->link;
	cout << "Target: ";
	printList(target);
	cout << "Splicing L2 at target in L1" << endl;
	splice(head2, target);
	cout << "L1: ";
	printList(head1);
	cout << "L2: ";
	printList(target->link);



	cout << "=====================" << endl << endl;
	cout << "Part Two:" << endl << endl;

	Node *head3 = nullptr; //head3 points to the first Node of the target List
	listInsertHead(6, head3);
	listInsertHead(5, head3);
	listInsertHead(4, head3);
	listInsertHead(2, head3);
	listInsertHead(3, head3);
	listInsertHead(2, head3);
	listInsertHead(3, head3);
	listInsertHead(2, head3);
	listInsertHead(1, head3); //1 2 3 2 3 2 4 5 6
	cout << "Target: ";
	printList(head3);
	cout << endl;

	Node *sublist1 = nullptr;
	listInsertHead(1, sublist1); //1
	cout << "Attempt match: ";
	printList(sublist1);
	if (isSubList(head3, sublist1) != nullptr)
		printList(isSubList(head3, sublist1));

	Node *sublist2 = nullptr;
	listInsertHead(9, sublist2);
	listInsertHead(3, sublist2); //3 9
	cout << "Attempt match: ";
	printList(sublist2);
	if (isSubList(head3, sublist2) != nullptr)
		printList(isSubList(head3, sublist2));

	Node *sublist3 = nullptr;
	listInsertHead(3, sublist3);
	listInsertHead(2, sublist3); //2 3
	cout << "Attempt match: ";
	printList(sublist3);
	if (isSubList(head3, sublist3) != nullptr)
		printList(isSubList(head3, sublist3));

	Node *sublist4 = nullptr;
	listInsertHead(6, sublist4);
	listInsertHead(5, sublist4);
	listInsertHead(4, sublist4);
	listInsertHead(2, sublist4); //2 4 5 6
	cout << "Attempt match: ";
	printList(sublist4);
	if (isSubList(head3, sublist4) != nullptr)
		printList(isSubList(head3, sublist4)); //multiple instances of 2

	Node *sublist5 = nullptr;
	listInsertHead(4, sublist5);
	listInsertHead(2, sublist5);
	listInsertHead(3, sublist5);
	listInsertHead(2, sublist5); //2 3 2 4
	cout << "Attempt match: ";
	printList(sublist5);
	if (isSubList(head3, sublist5) != nullptr)
		printList(isSubList(head3, sublist5)); //multiple instances of 2

	Node *sublist6 = nullptr;
	listInsertHead(7, sublist6);
	listInsertHead(6, sublist6);
	listInsertHead(5, sublist6); //5 6 7
	cout << "Attempt match: ";
	printList(sublist6);
	//if (isSubList(head3, sublist6) != nullptr)
	//	printList(isSubList(head3, sublist6)); //beyond scope of L1

	system("pause");
}