700608. Insert in Sorted way in a Sorted DLL
Medium
Insert in Sorted way in a Sorted DLL
Slug: insert-in-sorted-way-in-a-sorted-dll Difficulty: Medium Id: 700608 Topic Tags: doubly-linked-list, Linked List, Data Structures Company Tags: None
Summary
Given a sorted doubly linked list (DLL), the task is to insert a new node in a way that maintains the sorted order of the DLL. The problem requires an efficient algorithmic approach to handle insertion and maintain the sorted property.
Detailed Explanation
To solve this problem, we'll follow these steps:
- Find the correct position: Iterate through the DLL to find the correct position where the new node should be inserted. This is because the DLL is already sorted, so we need to find the node that comes before our new node in the sorted order.
- Update links: Once we've found the correct position, update the links of the adjacent nodes to point to our new node.
Here's a step-by-step breakdown:
- Start at the head of the DLL and iterate through each node until you find the correct position.
- When you find the correct position, create a new node with the given data.
- Update the
prevlink of the new node to point to the previous node in the DLL. - Update the
nextlink of the previous node to point to the new node. - If the new node is inserted at the beginning of the DLL (i.e., it's smaller than all existing nodes), update the head of the DLL to point to the new node.
Time complexity: O(n) Space complexity: O(1)
Optimized Solutions
Java
public class SortedDLL {
public static void insert(Node head, int data) {
Node newNode = new Node(data);
if (head == null || head.data >= data) {
// Insert at the beginning of the DLL
newNode.next = head;
head.prev = newNode;
head = newNode;
} else {
Node current = head;
while (current.next != null && current.next.data < data) {
current = current.next;
}
// Update links
newNode.prev = current;
newNode.next = current.next;
if (newNode.next != null) {
newNode.next.prev = newNode;
} else {
head = newNode;
}
}
}
}