Inserting a Node Into a Sorted Doubly Linked List
hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem
#include <bits/stdc++.h> | |
using namespace std; | |
class DoublyLinkedListNode { | |
public: | |
int data; | |
DoublyLinkedListNode *next; | |
DoublyLinkedListNode *prev; | |
DoublyLinkedListNode(int node_data) { | |
this->data = node_data; | |
this->next = nullptr; | |
this->prev = nullptr; | |
} | |
}; | |
class DoublyLinkedList { | |
public: | |
DoublyLinkedListNode *head; | |
DoublyLinkedListNode *tail; | |
DoublyLinkedList() { | |
this->head = nullptr; | |
this->tail = nullptr; | |
} | |
void insert_node(int node_data) { | |
DoublyLinkedListNode* node = new DoublyLinkedListNode(node_data); | |
if (!this->head) { | |
this->head = node; | |
} else { | |
this->tail->next = node; | |
node->prev = this->tail; | |
} | |
this->tail = node; | |
} | |
}; | |
void print_doubly_linked_list(DoublyLinkedListNode* node, string sep, ofstream& fout) { | |
while (node) { | |
fout << node->data; | |
node = node->next; | |
if (node) { | |
fout << sep; | |
} | |
} | |
} | |
void free_doubly_linked_list(DoublyLinkedListNode* node) { | |
while (node) { | |
DoublyLinkedListNode* temp = node; | |
node = node->next; | |
free(temp); | |
} | |
} | |
// Complete the sortedInsert function below. | |
/* | |
* For your reference: | |
* | |
* DoublyLinkedListNode { | |
* int data; | |
* DoublyLinkedListNode* next; | |
* DoublyLinkedListNode* prev; | |
* }; | |
* | |
*/ | |
DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) { | |
if(head==nullptr) return new DoublyLinkedListNode{data}; | |
auto p = head; | |
while(p != nullptr) | |
{ | |
if(p->data > data) | |
{ | |
// Insert | |
auto temp = new DoublyLinkedListNode{data}; | |
temp->prev = p->prev; | |
temp->next = p; | |
p->prev = temp; | |
if(p==head) return temp; | |
temp->prev->next = temp; | |
return head; | |
} | |
if(p->next == nullptr) break; | |
p = p->next; | |
} | |
p->next = new DoublyLinkedListNode{data}; | |
p->next->prev = p; | |
return head; | |
} | |
int main() |