Description
Given a linked list of length N, where the last node points to the M-th node in the list. Note that when M equals 0, it indicates that the last node points to NULL.
Your task is to get an input T and perform T deletion operations.
For each operation, you need to delete the first node with value V equal to A in the list. If no such node is found in the list, skip this operation.
After completing all operations, output each node's value in the linked list once, starting from the head.
If the linked list is empty, output "EMPTY!!!"
Example Operation 1:
Delete a node with value 2.
Delete a node with value 5.
Example Operation 2:
Delete a node with value 5.
Other Example Operation:
This question is a partial judge.
Please implement functions defined in the header file.
- getCycleEnd: returns the end node of the cycle, that is, the node whose next node is the start node of the cycle in Tortoise and Hare algorithm, in the linked list (if there is no cycle in the linked list, returns NULL)
- deleteNode: gets an input T and perform T deletion operations
Input
The first line contains two integers N and M, where N represents the length of the linked list, and the last node in the linked list points to the M-th node.
The second line contains N integers Vi , representing the value of the i-th node.
The third line contains one integer T, representing T insertion operations to be performed.
The following T lines each contain one integers A, indicating to delete the first node with value V equal to A.
Constraints
- 1 ≤ N ≤ 106
- 0 ≤ M ≤ N
- 1 ≤ T ≤ 100
- -109 ≤ A, V ≤ 109
Subtasks
- Testcases 1 ~ 5: 0 ≤ V ≤ 106, V is unique, M = 0
- Testcases 6 ~ 8: 0 ≤ V ≤ 106, V is unique
- Testcases 9 ~ 10: No additional restrictions
Output
After completing all operations, output each node's value in the linked list once, starting from the head.
If the linked list is empty, output "EMPTY!!!"
Please remember to print "\n" at the end.
Hint
You should use the Tortoise and Hare algorithm to pass testcases 6~10.
To complete this problem, the following cases should be taken care of:
- Case 1: delete the first node (head) of the linked list.
- Case 2: delete the first node and nodes at the start of the cycle.
- Case 3: delete the first node and nodes at the end of the cycle.
- Case 4: delete the first node, cycle start/end node, and self-loop node.
To check if you've handled these cases properly, testcases 6~10 are designed in following rules:
- Testcase 6: no cases above will occur.
- Testcase 7: Case 1 will occur.
- Testcase 8: Case 1~3 will occur.
- Testcase 9 and Testcase 10: Case 1~4 will occur.