Insert in Sorted way in a Sorted DLL | Linked Lists | MEDIUM

[@galepraveen]

Node* sortedInsert(Node* head, int x) { Node* newNode = getNode(x); // case -1, x < head->data if(x < head->data){ newNode->next = head; head->prev = newNode; return newNode; } // case-2, x lies in between Node* prevNode = head, *currNode = head->next; while(currNode != NULL){ if(prevNode->data next = newNode; newNode->prev = prevNode; newNode->next = currNode; currNode->prev = newNode; return head; } prevNode = currNode; currNode = currNode->next; } prevNode->next = newNode; newNode->prev = prevNode; return head; }

[@galepraveen]

Solved using Binary search too, if you’d like to see the code and learn…Here it is: Node* getTail(Node* head){ while(head->next){ head = head->next; } return head; } Node* getMidNode(Node* start, Node* end){ if(!start || start == end) return start; Node* slow = start, *fast = start; while(fast != end){ slow = slow->next; fast = fast->next; if(fast != end) fast = fast->next; } return slow; } class Solution { public: Node* sortedInsert(Node* head, int x) { Node* newNode = getNode(x); if(x < head->data){ newNode->next = head; head->prev = newNode; return newNode; } Node* start = head, *end = getTail(head); if(x > end->data){ end->next = newNode; newNode->prev = end; return head; } // Node* mid = getMidNode(start, end); // cout data prev; } } // // cout next = end; return head; }