Data Structures: Circular Linked List (Split Halves & Josephus Problem)

Implement a CircularLinkedList in C++ with advanced pointer manipulations:

• ◦
  Node* head where the last node's next points back to head.

• ◦
  void insert(int val): Inserts a node while maintaining circular tail-to-head linking.
• ◦
  bool deleteNode(int val): Deletes a node (handling head deletion, middle deletion, and single-node list) without breaking the circular cycle.
• ◦
  void display() const: Traverses the circular list using do-while loop and prints until returning to head.
• ◦
  void splitIntoTwoHalves(CircularLinkedList& firstHalf, CircularLinkedList& secondHalf): Uses fast and slow pointers to split the circular list into two independent circular sub-lists.

• ◦
  int solveJosephus(int n, int k): Simulates the historical Josephus Circle Elimination:
• ◦
  Construct a circular list of $n$ people numbered 1 to $n$.
• ◦
  Traverse the circle and eliminate every $k$-th person until only 1 survivor remains.
• ◦
  Return the survivor's number.

• ◦
  Create circular list with [10, 20, 30, 40, 50, 60].
• ◦
  Display circular chain.
• ◦
  Split into two halves and display both circular sub-lists ([10, 20, 30] and [40, 50, 60]).
• ◦
  Run solveJosephus(7, 3) (with 7 people eliminating every 3rd, survivor is person 4).