We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Linked Lists
  4. Inserting a Node Into a Sorted Doubly Linked List
  5. Discussions

Inserting a Node Into a Sorted Doubly Linked List

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 783 Discussions, By:

votes

Please Login in order to post a comment

  • 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;
        }
    }
    
    60|
    Permalink
  • chetangautam 5 years ago+ 0 comments

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

    53|
    Permalink
  • 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.

    32|
    Permalink
  • 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?

    15|
    Permalink
  • 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;
        }
    
    8|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature