ListNode* Solution::insertionSortList(ListNode* A)
{
vector<ListNode*> store;
store.push_back(A);
ListNode* iter=A->next;
ListNode* prev=A;
while(iter!=NULL)
{
if(iter->val>=prev->val)
{
store.push_back(iter);
prev=iter;
iter=iter->next;
}
else if(iter->valval)
{
int key=iter->val;
for(int i=store.size()-1; i>=0; i–)
{
if(store[i]->val<=key) break;
else if(store[i]->val>key)
{
int k=store[i]->val;
store[i]->val=key;
store[i]->next->val=k;
}
}
store.push_back(iter);
prev=iter;
iter=iter->next;
}
}
return A;
}
Why this insertion code doesnot work?
please reply fast//////////
/* C program for insertion sort on a linked list */
#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
#include
/* Link list node /
struct Node
{
int data;
struct Node next;
};
vector insertionSortList(Node* A)
{
vector<Node*> store;
store.push_back(A);
ListNode* iter=A->next;
ListNode* prev=A;
while(iter!=NULL)
{
if(iter->val>=prev->val)
{
store.push_back(iter);
prev=iter;
iter=iter->next;
}
else if(iter->val>prev->val)
{
int key=iter->val;
for(int i=store.size()-1; i>=0; i–-)
{
if(store[i]->val<=key) break;
else if(store[i]->val>key)
{
int k=store[i]->val;
store[i]->val=key;
store[i]->next->val=k;
}
}
store.push_back(iter);
prev=iter;
iter=iter->next;
}
}
return A;
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
/* A utility function to insert a node at the beginning of linked list /
void push(struct Node* head_ref, int new_data)
{
/* allocate node /
struct Node new_node = new Node;
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver program to test above functions
int main()
{
struct Node *a = NULL;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
printf("Linked List before sorting \n");
printList(a);
insertionSortList(&a);
printf("\nLinked List after sorting \n");
printList(a);
return 0;
}
reply as soon as possible
i am unable to implement it.
Is it possible to use
vector<Node*> store;
store.push_back(A);
dont use extra space.
i assume u know insertion sort.
what u can do is iterate ur given list from start to end and append ur current node in new list.
logic for appending ur current node to new list ->
check whether ur new list is empty or not . if it is empty then simply make ur current node as head node.
if newlist is not empty then iterate from start of newlist till ur current node value is greater than the node in new list.
where this conditon fails insert ur node at that point.
refer this->logic
i am unable to understand that code
why are we using head->next=null in line 6
this peice of code is still confusing
if(newList == NULL || newList->val >= current->val){
ListNode* temp = newList;
newList = current;
newList->next = temp;
}
if input is
4 10 5 9 12
see here if our newlist is null that means we havent constructed any list till now .
thats why we are adding assigning current to new list.
another case is if our newList is not null but the data at the starting node(of newlist) is bigger than the data of current node (of given node) that means we we need to insert current node at the start, thats is the reason wwhy that condtion is mentioned,
and the code in that condtion is just adding current node to the start
still not able to understand
have u studied insertion sort?
it is same ,only difference is instead of iterating from end to start , we are interating from start to end of newlist for finding insertion list
ok bhaiya…
video is really helpful Thank you.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.