#include <iostream>

using namespace std;

template <class T>

class List
{
private:
struct Node
{
T data;
Node* next;
Node(T const val)
{
data = val;
next = nullptr;
}
};

Node* head;

void printRec(Node* temp) const // O(n)

{
if (!temp)
return;
printRec(temp->next);
cout << temp->data << " ";
}
// Split the list into two halves and return the head of the second half
Node* splitList(Node* source)
{
if (!source || !source->next)
return nullptr;

Node* slow = source;

Node* fast = source->next;

while (fast && fast->next)

{
slow = slow->next;
fast = fast->next->next;
}

Node* secondHalf = slow->next;

slow->next = nullptr; // Split the list into two halves
 return secondHalf;
}

// Merge two sorted linked lists and return the head of the merged list
Node* mergeLists(Node* l1, Node* l2)
{
Node dummy(0);
Node* temp = &dummy;

while (l1 && l2)

{
if (l1->data <= l2->data)
{
temp->next = l1;
l1 = l1->next;
}
else
{
temp->next = l2;
l2 = l2->next;
}
temp = temp->next;
}

temp->next = l1 ? l1 : l2; // Append the remaining nodes

return dummy.next;
}

// Recursive merge sort function

Node* mergeSort(Node* node)
{
if (!node || !node->next) // Base case: empty list or single node
return node;

Node* secondHalf = splitList(node); // Split the list into two halves

// Recursively sort both halves

Node* left = mergeSort(node);
Node* right = mergeSort(secondHalf);

// Merge the two sorted halves

return mergeLists(left, right);
}
public:
List()
{
head = nullptr;
}

void insertAtStart(T const element) // O(1)

{
Node* newElem = new Node(element);
newElem->next = head;
head = newElem;
}

void insertAtEnd(T const element) // O(n)

{
Node* newElem = new Node(element);
if (!head)
{
head = newElem;
return;
}
Node* temp = head;
while (temp->next)
{
temp = temp->next;
}
temp->next = newElem;
}

void print() const // O(n)

{
if (!head)
{
cout << "Empty List";
return;
}
Node* temp = head;
while (temp)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
bool search(T const& element) const // O(n)
{
Node* temp = head;
while (temp)
{
if (temp->data == element)
{
return true;
}
temp = temp->next;
}
return false;
}

bool isEmpty() const // O(1)

{
return (!head);
}

void printrev() const // O(n)

{
printRec(head);
}

void printNth(int index) const // O(n)

{
if (index <= 0)
{
cout << "Invalid index!";
return;
}
Node* temp = head;
for (int i = 1; i < index; i++)
{
if (temp == nullptr)
{
cout << "Index out of bounds!";
return;
}
temp = temp->next;
}
if (temp == nullptr)
{
 cout << "Index out of bounds!";
}
else
{
cout << temp->data;
}
}

void deleteAtStart() // O(1)

{
if (!head)
{
cout << "Empty List! ";
return;
}
Node* temp = head->next;
delete head;
head = temp;
}

void deleteAtTail() // O(n)

{
if (!head)
{
cout << "Empty List!";
return;
}
if (!(head->next))
{
delete head;
head = nullptr;
return;
}
Node* temp = head;
while (temp->next && temp->next->next)
{
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}

void deleteFirstOccurrence(T val) // O(n)

{
 if (!head)
{
cout << "Empty List!";
return;
}
// Case 1: If the value is in the head node
if (head->data == val)
{
Node* temp = head;
head = head->next;
delete temp;
cout << "Element deleted successfully\n";
return;
}

// Case 2: Traverse the list to find the value

Node* temp = head;
while (temp->next)
{
if (temp->next->data == val)
{
Node* toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
cout << "Element deleted successfully\n";
return;
}
temp = temp->next;
}

// Case 3: Value not found

cout << "Element not found\n";
}

void reverseLLI()
{
if (!head || !(head->next)) // If the list is empty or has only one node, no need to reverse
return;

Node* prev = NULL;

Node* curr = head;
Node* forward = NULL;
while (curr)
{
 forward = curr->next; // Save the next node
curr->next = prev; // Reverse the current node's pointer
prev = curr; // Move prev forward
curr = forward; // Move curr forward
}

head = prev; // Update the head to point to the new head of the reversed list
}
void removeDuplicates()
{
if (!head || !(head->next)) // If the list is empty or has only one node
return;

Node* current = head;

while (current && current->next)

{
if (current->data == current->next->data)
{
// Duplicate found, remove it
Node* duplicate = current->next;
current->next = duplicate->next; // Skip the duplicate node
delete duplicate; // Free memory
}
else
{
// Move to the next node only if no duplicate is found
current = current->next;
}
}
}
void mergeTwoSortedLists(List<T>& l1, List<T>& l2)
{
// Create a dummy node to simplify the merging process
Node* dummy = new Node(0);
Node* temp = dummy;

Node* t1 = l1.head; // Pointer for the first list

Node* t2 = l2.head; // Pointer for the second list

// Merge the two lists by reusing nodes

while (t1 && t2)
{
if (t1->data <= t2->data)
 {
temp->next = t1;
t1 = t1->next;
}
else
{
temp->next = t2;
t2 = t2->next;
}
temp = temp->next;
}

// Append the remaining nodes from either list

temp->next = t1 ? t1 : t2;

// Update the head of the merged list

head = dummy->next;

// Delete the dummy node

delete dummy;

// Clear the input lists to avoid dangling pointers

l1.head = nullptr;
l2.head = nullptr;
}
void sortList()
{
head = mergeSort(head); // Call the merge sort function on the list
}
~List() // O(n)
{
while (head)
deleteAtStart();
}
void printNthFromTheEnd(int n) const
{
if (n <= 0)
{
cout << "Invalid Position";
return;
}
if (!head)
{
cout << "Empty List";
 return;
}
Node* fast = head;
Node* slow = head;
for (int i = 1; i <= n; i++)
{
if (!fast)
{
cout << "Position out of bounds";
return;
}
fast = fast->next;
}
while (fast)
{
fast = fast->next;
slow = slow->next;
}
cout << slow->data;
}
void removeNthFromTheEnd(int n) const
{
if (n <= 0)
{
cout << "Invalid Position";
return;
}
if (!head)
{
cout << "Empty List";
return;
}
Node* fast = head;
Node* slow = head;
for (int i = 1; i <= n; i++)
{
if (!fast)
{
cout << "Position out of bounds";
return;
}
fast = fast->next;
}
 // Special case: removing the head node (1st from end = last, 2nd from end = second last,
etc.)
// If fast is null after n steps, we need to remove the head
if (!fast)
{
Node* temp = head;
head = head->next;
delete temp;
cout << "Element removed successfully\n";
return;
}
// Move both pointers until fast reaches the last node
// We want slow to be one position before the node to delete
while (fast->next)
{
fast = fast->next;
slow = slow->next;
}
Node* delNode = slow->next;
slow->next = slow->next->next;
delete slow->next;
cout << "Element removed successfully\n";
}

/*Given the head of a linked list and a value x, partition it such that all nodes less than x
come before nodes greater than or equal to x.You should preserve the original relative
order of the nodes in each of the two partitions.*/
void partitionList(T n)
{
if (!head || !head->next)// Empty list or single node, nothing to partition
return;

Node* small = new Node(T{});

Node* large = new Node(T{});
Node* smallp = small;
Node* largep = large;
while (head)
{
if (head->data < n)
{
smallp->next = head;
smallp = smallp->next;
}
else
 {
largep->next = head;
largep = largep->next;
}
head = head->next;
}
smallp->next = large->next;
largep->next = nullptr;
head = small->next;
delete small;
delete large;
}
void reorderList() // O(n) time, O(1) space
{
if (!head || !head->next || !head->next->next)
return; // Less than 3 nodes, no reordering needed

// Step 1: Find the middle of the list using slow-fast pointers

Node* slow = head;
Node* fast = head;

while (fast->next && fast->next->next)

{
slow = slow->next;
fast = fast->next->next;
}

// Step 2: Split the list into two halves

Node* secondHalf = slow->next;
slow->next = nullptr; // Break the connection

// Step 3: Reverse the second half

Node* prev = nullptr;
Node* curr = secondHalf;

while (curr)
{
Node* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
secondHalf = prev; // Now secondHalf points to reversed second half
 // Step 4: Merge the two halves alternately (SIMPLIFIED)
Node* list1 = head; // Points to first half
Node* list2 = secondHalf; // Points to reversed second half

while (list2) // Continue until second list is exhausted

{
// Save the next nodes before we lose them
Node* next1 = list1->next;
Node* next2 = list2->next;

// Connect: list1 -> list2 -> next1

list1->next = list2;
list2->next = next1;

// Move to the next pair

list1 = next1;
list2 = next2;
}
}
void oddEvenList() // O(n) time, O(1) space
{
if (!head || !head->next)
return; // Empty list or single node

Node* odd = head; // Points to current odd-indexed node

Node* even = head->next; // Points to current even-indexed node
Node* evenHead = even; // Save the head of even list to connect later

// Single traversal to separate odd and even indexed nodes

while (even && even->next)
{
// Connect odd nodes together
odd->next = even->next;
odd = odd->next;

// Connect even nodes together

even->next = odd->next;
even = even->next;
}

// Connect odd list to even list

odd->next = evenHead;
}
void rotateList(int k)
 {
// Handle edge cases: empty list, single node, or no rotation needed
if (!head || !head->next || k == 0)
return; // Nothing to rotate

// Step 1: Find the length of the list and get the tail pointer
Node* tail = head; // Start from head to traverse entire list
int length = 1; // Count starts at 1 (for head node)

// Traverse to end while counting nodes

while (tail->next)
{
tail = tail->next; // Move to next node
length++; // Increment node counter
}
// Now: tail points to last node, length = total nodes

// Step 2: Optimize k to handle cases where k > length

k = k % length; // If k=7 and length=5, effective rotation is k=2
if (k == 0)
return; // After modulo, if k=0, no rotation needed

// Step 3: Create a circular list by connecting tail to head

tail->next = head; // Make last node point to first node (circular)

// Step 4: Find the new tail position (where to break the circle)
Node* temp = head; // Start from current head
// Move (length - k) steps to find new tail
// Example: length=5, k=2 → move 3 steps → new tail at position 3
for (int i = 0; i < length - k; i++)
{
temp = temp->next; // Move one step forward
}
// Now: temp points to the new tail (last node of rotated list)

// Step 5: Set new head and break the circular connection

head = temp->next; // New head is next node after new tail
temp->next = NULL; // Break the circle at new tail

// Result: List is now rotated k positions to the right

}
// Approach 1: Count and Replace (2-pass algorithm)
// Time: O(2n) = O(n), Space: O(1)
void sort012f() // sort ll containing 0s,1s and 2s . Time O(2n) Space O(1)
{
// Handle edge cases: empty list or single node
if (!head || !head->next)
return;
// First pass: Count occurrences of 0s, 1s, and 2s
Node* temp = head;
int countZero = 0, countOne = 0, countTwo = 0;
while (temp)
{
if (temp->data == 0)
countZero++;
else if (temp->data == 1)
countOne++;
else
countTwo++;
temp = temp->next;
}
// Second pass: Replace node values based on counts
temp = head;
while (temp)
{
if (countZero)
{
temp->data = 0;
countZero--;
}
else if (countOne)
{
temp->data = 1;
countOne--;
}
else
{
temp->data = 2;
countTwo--;
}
temp = temp->next;
}
}
// Approach 2: Node Rearrangement (1-pass algorithm)
// Time: O(n), Space: O(1) - excluding dummy nodes
Node* sortLinkedList012_NodeRearrangement()
{
// Handle edge cases: empty list or single node
if (!head || !head->next)
return head;

// Create dummy heads for three separate lists

Node* zeroHead = new Node(-1); // Dummy head for 0s
Node* oneHead = new Node(-1); // Dummy head for 1s
Node* twoHead = new Node(-1); // Dummy head for 2s

// Keep track of tail pointers for each list

Node* zero = zeroHead;
Node* one = oneHead;
Node* two = twoHead;

// Single pass: Distribute nodes into three separate lists

Node* temp = head;
while (temp)
{

if (temp->data == 0)
{
zero->next = temp;
zero = temp; // Move tail pointer
}
else if (temp->data == 1)
{
one->next = temp;
one = temp; // Move tail pointer
}
else // temp->data == 2
{
two->next = temp; // FIXED: Was == instead of =
two = temp; // Move tail pointer
}

temp = temp->next;
}

// Connect the three lists: 0s -> 1s -> 2s

// Handle case where some lists might be empty
zero->next = (oneHead->next != nullptr) ? oneHead->next : twoHead->next;
one->next = twoHead->next;
two->next = nullptr; // Terminate the final list

// Store the new head (skip dummy node)

 Node* newHead = zeroHead->next;

// Clean up dummy nodes to prevent memory leaks

delete zeroHead;
delete oneHead;
delete twoHead;

return newHead;
}
// Approach 3: Optimal Solution - Reverse Second Half
// Time: O(n), Space: O(1)
bool isPalindrome_Optimal(Node* head) {
if (!head || !head->next)
return true;

// Step 1: Find the middle of the linked list

Node* slow = head;
Node* fast = head;

while (fast->next && fast->next->next) {

slow = slow->next; // Move 1 step
fast = fast->next->next; // Move 2 steps
}

// Step 2: Reverse the second half

Node* secondHalf = reverseList(slow->next);

// Step 3: Compare first half with reversed second half

Node* firstHalf = head;
Node* temp = secondHalf; // Keep reference for restoration

bool isPalin = true;

while (secondHalf) { // Second half might be shorter
if (firstHalf->val != secondHalf->val) {
isPalin = false;
break;
}
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}

// Step 4: Restore the original list (optional but good practice)

slow->next = reverseList(temp);
 return isPalin;
}

private:
// Helper function to reverse a linked list
Node* reverseList(ListNode* head) {
Node* prev = nullptr;
Node* curr = head;

while (curr) {
Node* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}

return prev;
}
};

int main()
{
List<int> L1;
L1.insertAtStart(4);
L1.insertAtStart(7);
L1.insertAtStart(9);
L1.insertAtStart(7);
L1.insertAtEnd(2);
L1.insertAtStart(3);
L1.insertAtStart(3);
L1.insertAtStart(7);
L1.insertAtStart(1);
cout << "List:\t";
L1.print();

if (L1.search(2))
cout << "\nElement is present\n";
else
cout << "\nElement is not present\n";

if (L1.search(19))
cout << "\nElement is present\n";
else
cout << "\nElement is not present\n";
cout << "\nList in reverse:\t";
L1.printrev();

cout << "\nThe element on 8th index is:\t";

L1.printNth(8);

cout << "\n\nDeleteAtStart\t";

L1.deleteAtStart();
L1.print();

cout << "\nDeleteAtEnd:\t";

L1.deleteAtTail();
L1.print();

cout << "\nDeleteFirstOccurrence (7):\t";

L1.deleteFirstOccurrence(7);
L1.print();

cout << "\nDeleteFirstOccurrence (15):\t";

L1.deleteFirstOccurrence(15); // Element not found

L1.reverseLLI();
L1.print();

List<int> L2;
List<int> L3;

// Create first sorted linked list

L2.insertAtEnd(1);
L2.insertAtEnd(3);
L2.insertAtEnd(5);
L2.insertAtEnd(7);

// Create second sorted linked list

L3.insertAtEnd(2);
L3.insertAtEnd(4);
L3.insertAtEnd(6);
L3.insertAtEnd(8);

cout << "List 2:\t";

L2.print();

cout << "List 3:\t";

 L3.print();

// Merge the two sorted lists

List<int> mergedList;
mergedList.mergeTwoSortedLists(L2, L3);

cout << "Merged List:\t";

mergedList.print();

// Verify that the original lists are empty

cout << "Original List 1 (after merge): ";
L2.print();
cout << "\nOriginal List 2 (after merge): ";
L3.print();

return 0;
}