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.
  1. Prepare
  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

  • RodneyShag
     + 12 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.