Insert in Sorted way in a Sorted DLL

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Insert a node in sorted doubly linked list maintaining sorted order.

Algorithm

1Traverse to find correct position. Insert before first node with value >= new value.

Common Pitfalls

•Update both prev and next pointers of adjacent nodes. Handle insertion at head.

Insert in Sorted way in a Sorted DLL.java

Java

// Approach: Traverse the sorted DLL to find the correct position, then update pointers.
// Time: O(n) Space: O(1)
class Solution {
    public Node sortedInsert(Node head, int x) {
        Node newNode = new Node(x);
        if (head == null || head.data >= x) {
            newNode.next = head;
            return newNode;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data < x)
            temp = temp.next;

        newNode.next = temp.next;
        temp.next = newNode;
        return head;
    }
}

Was this solution helpful?