Insert in Sorted way in a Sorted DLL | GeeksForGeeks | Problem of the Day

[@mathematics3398]

Table of Contents
0:00 Problem Statement
0:35 Solution
6:30 Pseudo Code
9:32 Code - Python
10:57 Code - C++

[@mathematics3398]

class Solution:
#Function to insert a node in a sorted doubly linked list.
def sortedInsert(self, head, x):
NEW = Node(x)
if not head:
return NEW
ptr = head
prvs = None
while ptr and ptr.data < x:
prvs = ptr;
ptr = ptr.next
if ptr:
ptr = ptr.prev
if not ptr and not prvs:
NEW.next = head
head.prev = NEW
head = NEW
elif not ptr:
prvs.next = NEW
NEW.prev = prvs
else:
NEW.next = ptr.next
NEW.prev = ptr
if ptr.next:
ptr.next.prev = NEW
ptr.next = NEW
return head

[@mathematics3398]

class Solution {
public:
Node* sortedInsert(Node* head, int x) {
Node *NEW = getNode(x);
if (!head)
return NEW;
Node *ptr = head, *prvs = nullptr;
while (ptr and ptr->data < x) {
prvs = ptr;
ptr = ptr->next;
}
if (ptr)
ptr = ptr->prev;
// first node
if (!ptr and !prvs) {
NEW->next = head;
head->prev = NEW;
head = NEW;
}
else {
// last node
if (!ptr) {
prvs->next = NEW;
NEW->prev = prvs;
}
//in middle
else {
NEW->next = ptr->next;
NEW->prev = ptr;
if (ptr->next)
ptr->next->prev = NEW;
ptr->next = NEW;
}
}
return head;
}
};