Write an algorithm (in C++) for inserting a node in between k-1 node and k-th no

Question

Write an algorithm (in C++) for inserting a node in between k-1 node and k-th node on a singly linked list. After the insertion, your function returns the pointer which points to the head of the list. If the present linked list has less than k nodes, the node should be inserted as the last node on the list when it is done. The node is defined as struct node {int INFO; node *NEXT ; Your algorithm needs to meet all conditions as follows: (a) if the list is empty; (b) if the node is the first node on the list (k=1 ); (c) if the node is the last node on the list; (d) if the number of nodes on the list are less than k; (e) Assume the head pointer of the list is HEAD

Explanation / Answer

using namespace std; struct Node { int Data; Node* next; }; Node*getNode(int Data) { Node* newNode= (Node*)malloc(sizeof(Node)); newNode->Data=Data; newNode->next=NULL; } void insertAt(Node**HEAD_ref,int k) { if (*HEAD_ref <=k-1) *HEAD_ref= getNode(k); else { Node* newNode= getNode(k); Node*pend =*HEAD_ref; Node*end = (*HEAD_ref)->next; while (end &&end->next) { pend=pend->next; end=end->next->next; } newNode->next=pend->next; pend->next=newNode; } } void display(Node*HEAD) { while(HEAD !=NULL) { cout<<HEAD->DATA<<""; HEAD=HEAD->next; } } int main() { Node*HEAD =NULL; HEAD=getNode(1); HEAD->next->next=getNode(3); HEAD->next->next->next=getNode(4); HEAD->next->next->next->next=getNode(5); cout<<"Linked List before insertion:"; display(HEAD); int k=k-1; insertAt(&HEAD, k); cout<<" Linked list after insertion:"; display(HEAD); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.