@@ -0,0 +1,2045 @@
+package data_structures.linked_lists;%0D%0A%0D%0A/*%0D%0A * Problem Statement:%0D%0A * Youre given the pointer to the head node of a sorted doubly linked list and%0D%0A * an integer to insert into the list. Create a node and insert it into the%0D%0A * appropriate position in the list. The head node might be NULL to indicate%0D%0A * that the list is empty.%0D%0A * %0D%0A * Input Format:%0D%0A * You have to complete the Node* SortedInsert(Node* head, int data) method%0D%0A * which takes two arguments - the head of the sorted, doubly linked list and%0D%0A * the value to insert. You should NOT read any input from stdin/console.%0D%0A * %0D%0A * Output Format:%0D%0A * Create a node with the given data and insert it into the given list, making%0D%0A * sure that the new list is also sorted. Then return the head node of the%0D%0A * updated list. Do NOT print anything to stdout/console.%0D%0A * %0D%0A * Sample Input: %0D%0A * NULL , data = 2%0D%0A * NULL %3C-- 2 %3C--%3E 4 %3C--%3E 6 --%3E NULL , data = 5%0D%0A * %0D%0A * Sample Output: %0D%0A * NULL %3C-- 2 --%3E NULL%0D%0A * NULL %3C-- 2 %3C--%3E 4 %3C--%3E 5 %3C--%3E 6 --%3E NULL%0D%0A */%0D%0Apublic class InsertNodeIntoSortedDoublyLinkedList %7B%0D%0A%0D%0A%09DNode SortedInsert(DNode head,int data) %7B%0D%0A%09    DNode newNode = new DNode();%0D%0A%09    newNode.data = data;%0D%0A%09    %0D%0A%09    if (head == null) %7B%0D%0A%09        head = newNode;%0D%0A%09        newNode.next = null;%0D%0A%09        newNode.prev = null;%0D%0A%09        return head;%0D%0A%09    %7D else if (data %3C= head.data) %7B%0D%0A%09        newNode.next = head;%0D%0A%09        newNode.prev = null;%0D%0A%09        head = newNode;%0D%0A%09        return head;%0D%0A%09    %7D else %7B%0D%0A%09        DNode runner = head;%0D%0A%09        %0D%0A%09        while (runner.next != null) %7B%0D%0A%09            if (data %3C= runner.next.data) %7B%0D%0A%09                runner.next.prev = newNode;%0D%0A%09                newNode.next = runner.next;%0D%0A%09                runner.next = newNode;%0D%0A%09                return head;%0D%0A%09            %7D%0D%0A%09            runner = runner.next;%0D%0A%09        %7D%0D%0A%09        runner.next = newNode;%0D%0A%09        newNode.prev = runner;%0D%0A%09        newNode.next = null;%0D%0A%09        %0D%0A%09        return head;%0D%0A%09    %7D%0D%0A%09%7D%0D%0A%7D%0D%0A%0D%0Aclass DNode %7B%0D%0A%09int data;%0D%0A%09DNode next;%0D%0A%09DNode prev;%0D%0A%7D

Add InsertNodeIntoSortedDoublyLinkedList