Skip to content

Instantly share code, notes, and snippets.

@NicolaBernini
Created January 15, 2021 12:02
Show Gist options
  • Save NicolaBernini/4379d0ba54d24eed61e3e1ab3a9aeff2 to your computer and use it in GitHub Desktop.
Save NicolaBernini/4379d0ba54d24eed61e3e1ab3a9aeff2 to your computer and use it in GitHub Desktop.
Solution to Hackerrank Inserting a Node Into a Sorted Doubly Linked List

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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment