700540. Insert in a Sorted List
Insert in a Sorted List
Slug: insert-in-a-sorted-list
Difficulty: Easy
Id: 700540
Topic Tags: Linked List, Data Structures
Company Tags: Amazon, Wipro, SAP Labs
Summary
The problem "Insert in a Sorted List" involves inserting an element into a sorted linked list. The goal is to maintain the sorted order of the elements while performing the insertion. This problem requires understanding of basic linked list operations and algorithms for searching and updating the list.
Detailed Explanation
To solve this problem, we can use a simple iterative approach that starts from the beginning of the linked list and moves forward until it finds the correct position to insert the new element.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
currentandprev, both pointing to the head of the list. - Loop through the list until we find the correct position for insertion. If the current node is greater than the new element, move
prevone step forward and updatecurrent. - Once we've found the correct position (i.e., the current node is either null or less than the new element), insert the new element after the
prevnode. - Update the
nextpointer of the previous node to point to the new node.
Time complexity: O(n) where n is the number of elements in the list, as we need to traverse the entire list to find the correct position for insertion.
Space complexity: O(1), as we only use a constant amount of space to store the pointers and the new element.
Here's an ASCII art diagram illustrating the steps:
+---+ +---+ +---+
| A | -> | B | -> | C |
+---+ +---+ +---+
(initial state)
+---+ +---+ +---+
| A | -> | new | -> | B |
| | | | |
+---+ +---+ +---+
(after insertion)
Optimized Solutions
Java
public void insert(int value) {
ListNode current = head;
ListNode prev = null;
while (current != null && current.value < value) {
prev = current;
current = current.next;
}
ListNode newNode = new ListNode(value);
if (prev == null) {
head = newNode;
} else {
prev.next = newNode;
}
}