Note :
Testcase 6 has been modified please rejudge your code.
In this homework, you are asked to make a linked list data structure. You need to implement seven operations, i.e Insert, Insert_at, Pop_back, Pop_at, Reverse_All, Reverse, Print.
Notice: <string> is allowed, but other STL are not allowed
There are seven operations to be implemented.
1. Insert “string”
Insert a string of characters, such as "abcd", at the end of the linked list. Each character will be stored as a separate node in the list
Example:
Input: Insert abcd
Result: The list will become 'a' -> 'b' -> 'c' -> 'd'.
Input: Insert efgh
Result: The list will become 'a' -> 'b' -> 'c' -> 'd'-> 'e' -> ‘f' -> 'g' -> 'h'.
Note: The string consists only [0-9,A-Z,a-z].
2. Insert_at “string” P
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: 'a' -> 'b' -> 'c' -> 'd'
Input: Insert_at ef 2
Result: 'a' -> 'b' -> ’e’ -> ’f’ -> 'c' -> 'd''.
Note: If P is greater than the size of the linked list, insert the node at the end of linked list.
3. Pop_back
Remove the last node from the linked list.
Example:
List before operation: 'a' -> 'b' -> 'c' -> 'd'
Input: Pop_back
Result: 'a' -> 'b' -> 'c'.
4. Pop_at P
Remove the P’th node from the linked list.
Example:
List before operation: 'a' -> 'b' -> 'c' -> 'd'
Input : Pop_at 2
Result: 'a' -> 'c' -> 'd'.
Note: If P is greater than the size of the linked list, pop the node at the end of linked list.
5. Reverse_All
Reverse the entire linked list.
Example:
List before operation: 'a' -> 'b' -> 'c' -> 'd'
Input: Reverse_All
Result: The list becomes 'd' -> 'c' -> 'b' -> 'a'.
6. Reverse K
Group every K node in the linked list and then reverse them. If there are fewer than K nodes remaining at the end of the list, leave them unchanged.
Example.1:
List before operation: 'a' -> 'b' -> 'c' -> 'd' -> 'e' -> 'f' -> 'g'
Input: Reverse 3
Results: 'c' -> 'b' -> 'a' -> 'f' -> 'e' -> 'd' -> 'g'.
The last node 'g' remains unchanged because the last group has fewer than k nodes.
Example.2:
List before operation: 'a' -> 'b' -> 'c' -> 'd' -> 'e' -> 'f' -> 'g'
Input: Reverse 2
Results: ’b’ -> ’a’ -> ’d’ -> ’c’ -> ’f’ -> ’e’-> ’g’.
The last node 'g' remains unchanged because the last group has fewer than k nodes.
Note: If K is greater than the size of the linked list, don’t do anything.
7. Print
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.
There are M operations specified in the input lines and 0<M< 400000.
Parameters:
0 < P < 2000000
0 < K < 10000
For every operation “Print”, you need to output all characters stored in the linked list and shift a newline.