Discussion on Inserting a Node Into a Sorted Doubly Linked List Challenge

Sort 783 Discussions, By:

calvin_cheng_cc 5 years ago+ 0 comments

This worked for me (Java):

Node SortedInsert(Node head,int data) {
    Node n = new Node();
    n.data = data;
    if (head == null) {
        return n;
    }
    else if (data <= head.data) {
        n.next = head;
        head.prev = n;
        return n;
    }
    else {
        Node rest = SortedInsert(head.next, data);
        head.next = rest;
        rest.prev = head;
        return head;
    }
}

chetangautam 5 years ago+ 0 comments

This is wrong. Why do I see input as unsorted, when the problem mentions sorted.

RodneyShag 4 years ago+ 0 comments

Java Iterative solution - passes 100% of test cases

From my HackerRank solutions.

Runtime: O(n)
Space Complexity: O(1)

Node SortedInsert(Node head, int data) {
    /* Create Node to insert */
    Node newNode = new Node();
    newNode.data = data;
    
    if (head == null) { // insert in empty list
        return newNode;
    } else if (data < head.data) { // insert in front of list
        newNode.next = head;
        head.prev = newNode;
        return newNode;
    } else {
        /* Walk list with 2 pointers */
        Node n1 = null;
        Node n2 = head;
        while (n2 != null && n2.data < data) {
            n1 = n2;
            n2 = n2.next;
        }
        
        if (n2 == null) { // insert at end of list
            n1.next = newNode;
            newNode.prev = n1;
        } else { // insert in empty list
            n1.next = newNode;
            n2.prev = newNode;
            newNode.prev = n1;
            newNode.next = n2;
        }
        return head;
    }
}

Let me know if you have any questions.

charanacharyah 6 years ago+ 0 comments

Looks like there's an issue with the Java version. I submitted this,

Node newNode = new Node();
newNode.data = data;

if(head == null || head.data >= data){
    newNode.next = head;
    newNode.prev = null;
    return newNode;
}

Node current = head;
Node prev = null;
while(current != null && current.data < data){
    prev = current;
    current = current.next;
}

Node next = prev.next;
newNode.prev = prev;
newNode.next = next;
if(next != null){
    next.prev = newNode;
}

return head;

and I see that the condition head == null is never satisfied. Can someone help?

talsa 2 years ago+ 0 comments

static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {
        if (head == null)
            return new DoublyLinkedListNode(data);
        if(head.data > data) {
            DoublyLinkedListNode node = new DoublyLinkedListNode(data);
            node.next = head;
            return node;
        }
            head.next = sortedInsert(head.next, data);
            return head;
    }

Load more conversations