Please consider the following C++ code. Implement a singly linked list which has a certain function.
Fill in the blanks marked "//TODO"
#include <iostream>
using namespace std;
class MyLinkedList;
class ListNode {
friend MyLinkedList;
private:
int val;
ListNode *next;
public:
ListNode():val(0),next(0){};
friend MyLinkedList;
};
class MyLinkedList {
public:
/** Initialize your data structure here. */
MyLinkedList():length(0),first(0){};
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
//index is invalid
if (index > length-1)
return -1;
//Use if else statement to handle the cases where index is equal to 0 and index is greater than 0 respectively
else{
ListNode* node;
node = first;
if(index == 0){
return first->val;
}
else{
for (int i=0;i<index;i++){
node = node->next;
}
return node->val;
}
}
}
/** Add a node of value val before the index-th node in the linked list. If the index is equal to the length of the linked list, the node will be appended to the end of the linked list. If the index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
//index is invalid
if (index > length){}
//Hint : Use if else statement to handle the cases where index is equal to 0 and index is greater than 0 respectively
//TODO
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
//index is invalid
if (index > length-1){}
//Hint : Use if else statement to handle the cases where index is equal to 0 and index is greater than 0 respectively
//TODO
}
private:
int length;
ListNode* first;//Point to the first node in the linked list
};
int main (){
MyLinkedList* obj = new MyLinkedList();
string cmd;
while(cin >> cmd){
if(cmd == "addAtIndex"){
int x;
int y;
cin >> x;
cin >> y;
obj->addAtIndex(x,y);
}else if(cmd == "deleteAtIndex"){
int x;
cin >> x;
obj->deleteAtIndex(x);
}else if(cmd == "get"){
int x;
int y;
cin >> x;
y = obj->get(x);
cout<<y<<endl;
}
else if(cmd == "exit"){
return 0;
}
}
return 0;
}
Hint:
1. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
2. Assume the index of the link list always starts from 0.
3.MyLinkedList() Initializes the MyLinkedList object.
int get(int index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
void addAtIndex(int index, int val) : Add a node of value val before the index-th node in the linked list. If the index equals the length of the linked list, the node will be appended to the end of the linked list. If the index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) : Delete the indexth node in the linked list, if the index is valid.
4.If the program you submit wants to use “nullptr” to represent a null pointer, you can compile it with c++17 on OJ.
5.All input index parameters will be equal to or greater than zero.
Constraints:
1.. Please do not use the built-in LinkedList library.
Multiple lines of string
Use different function according to different string of command :
addAtIndex x y : call "addAtIndex" function with x as parameter index, y as parameter val
deleteAtIndex x : call "deleteAtIndex" function with x as parameter index
get x : call "get" function with x as parameter index
exit : Exit the program
When input command is get, the program will generate the corresponding output