Description
MAYA is a classic marble shooter game where players need to shoot colored marbles and try to eliminate the line of marbles. When three or more marbles of the same color are aligned, they will be eliminated.
In this quiz, you are asked to simulate a MAYA game with circular linked list.
There are three Input command you will need to implement.
Notice: <string> is allowed, but other STL are not allowed
1. Insert_at “string” P
Start from a dummy head pointer and insert a string of characters, such as "ef", at the specific location, after the P’th node, of the linked list.
Example:
List before operation: Empty
Input: Insert_at abcd 2
Result:
Explanation: Originally there is no node in the list, so we can’t find the second node.
Therefore, we insert “abcd” into the empty list, and keep the head pointer point the first character of the string, which is ‘a’. Note that it is a circular linked list, so you need to ensure that the head and tail is connected.
Example:
List before operation: 'a' -> 'b' -> 'c' -> 'd'
Input: Insert_at ef 7
Result:
Explanation: Insert the string of characters after the 7’th node. Note that the node that head pointer pointing at is the first node. So counting from abcdabc, the 7'th node is 'c'.
2. Pop_at P
Start from a dummy head pointer and remove the P’th node from the linked list.
Example:
List before operation: 'a' -> 'b' -> 'c' -> 'd'
Input : Pop_at 5
Result:
Explanation: The head pointer initially points to the 5th node. Before popping the 5th node, we move the head pointer to the node following the 5th node.
3. Print
Start from a dummy head node and print all the elements of the linked list in their current order, from the head node to the tail node.
Input Format: Print
List: 'a' -> 'b' -> 'c' -> 'd'
Result: abcd.
Rules of eliminating nodes: After the operation of “Insert_at” and “Pop_at”, you will need to check the linked list. Starting from the node head pointer pointing at and transverse the whole circular linked list, if three or more nodes of the same character are aligned, they will need to be eliminated.
Note: Keep in mind that this is a circular linked list, where the head and tail nodes are connected. You need to consider the edge cases carefully. Additionally, if you want to pop the node that the head pointer is currently pointing to, make sure to update the head pointer to the next node.
Example:
List after Insert_at or Pop at: ‘a’->‘b’->’c’->’c’->’c’->’b’->’d’
After eliminating nodes: a->‘b’->’b’->’d’
Example:
List after Insert_at or Pop at: ‘a’->‘b’->’c’->’c’->’c’->’b’->’b’->’d’
After eliminating nodes: ’a->‘b’->’b’->’b’->’d’
After eliminating nodes: ’a->’d’
Example:
List after Insert_at or Pop at: ‘a’->‘a’->’b’->’b’->’c’->’b’->’b’->’a’
After eliminating nodes: ’b’->’b’->’c’->’b’->’b’
After eliminating nodes: ‘c’
Example:
List after Insert_at or Pop at: ‘a’->‘b’->’c’->’c’->’c’->’b’->’b’->’b’->'b'->'d'
After eliminating nodes: a’->‘b’->'d'
Hint: If you trigger the elimination function, you will need to trigger it again to ensure that all the aligned nodes will be eliminated.
Input
There are M operations specified in the input lines and 0 < M < 300000.
Parameters:
0 < P < 2000000
Output
For every operation “Print”, you need to output all characters stored in the linked list and shift a newline.