700127. Sorted insert for circular linked list
Sorted Insert for Circular Linked List
Slug: sorted-insert-for-circular-linked-list
Difficulty: Medium
Id: 700127
Topic Tags: circular-linked-list, Linked List, Data Structures
Company Tags: Zoho, Amazon, Microsoft
Summary
Given a circular linked list and an integer value to be inserted in the sorted order. The task is to insert the given value in the correct position in the sorted circular linked list.
Detailed Explanation
To solve this problem, we need to maintain two pointers - prev and current. Initially, both are pointing at the head of the list. We start traversing the list from the head until we find a node whose data is greater than or equal to the value to be inserted. This node becomes our insertion point.
If the value to be inserted is less than the data of the head node, we need to check if it should be inserted at the end of the list or before the first node (since it's a circular linked list). We do this by moving prev and current until they meet. This ensures that we traverse the entire list.
Once we find our insertion point, we update the data of the node to which current is pointing to be equal to the value to be inserted. If the new node should come before the head, we need to update the head as well.
Here's a step-by-step breakdown:
- Initialize
prevandcurrentto point at the head of the list. - Traverse the list until you find a node whose data is greater than or equal to the value to be inserted.
- If the value to be inserted is less than the data of the head node, continue traversing the list until
prevandcurrentmeet. - Update the data of the node pointed by
currentto be equal to the value to be inserted. - If the new node should come before the head, update the head as well.
Time complexity: O(n), where n is the number of nodes in the list. Space complexity: O(1).
Optimized Solutions
Java
public class Node {
int data;
Node next;
public Node(int d) {
data = d;
next = null;
}
}
public void sortedInsert(Node head, int val) {
Node prev = head;
Node current = head;
do {
if (val <= current.data) {
prev.next = new Node(val);
prev = prev.next;
return;
}
prev = current;
current = current.next;
} while (prev != head && current != head);
if (val < head.data) {
prev.next = new Node(val);
} else {
head.data = val;
}
}