Given a sorted list in increasing order and a single node, insert the node into the list’s correct sorted position. The function should take an existing node and rearranges pointers to insert it into the list. For example,
Practice this problem
There are many possible solutions to this problem. The basic strategy is to iterate down the list looking for the place to insert the new node. That could be the end of the list or a point just before a larger node than the new node. The three solutions presented handle the “head end” case in different ways.
1. Naive Approach
The naive implementation can be seen below in C, Java, and Python:
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Helper function to return a new node of the linked list struct Node* newNode(int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Function to insert a given node at its correct sorted position into // a given list sorted in increasing order void sortedInsert(struct Node** head, struct Node* newNode) // special case for the head end if (*head == NULL || (*head)->data >= newNode->data) // locate the node before the point of insertion struct Node* current = *head; while (current->next != NULL && current->next->data < newNode->data) { newNode->next = current->next; int keys[] = {2, 4, 6, 8}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { sortedInsert(&head, newNode(5)); sortedInsert(&head, newNode(9)); sortedInsert(&head, newNode(1)); |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> NULL
Node(int data, Node next) // Helper function to print a given linked list public static void printList(Node head) System.out.print(ptr.data + " —> "); System.out.println("null"); // Function to insert a given node at its correct sorted position into // a given list sorted in increasing order public static Node sortedInsert(Node head, Node newNode) // special case for the head end if (head == null || head.data >= newNode.data) // locate the node before the point of insertion while (current.next != null && current.next.data < newNode.data) { newNode.next = current.next; public static void main(String[] args) int[] keys = {2, 4, 6, 8}; // points to the head node of the linked list // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); head = sortedInsert(head, new Node(5)); head = sortedInsert(head, new Node(9)); head = sortedInsert(head, new Node(1)); |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> null
def __init__(self, data=None, next=None): # Helper function to print a given linked list print(ptr.data, end=' —> ') # Function to insert a given node at its correct sorted position into # a given list sorted in increasing order def sortedInsert(head, newNode): # special case for the head end if head is None or head.data >= newNode.data: # Locate the node before the poof insertion while current.next and current.next.data < newNode.data: newNode.next = current.next if __name__ == '__main__': # points to the head node of the linked list # construct a linked list for i in reversed(range(len(keys))): head = Node(keys[i], head) head = sortedInsert(head, Node(5)) head = sortedInsert(head, Node(9)) head = sortedInsert(head, Node(1)) |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> None
2. Using Dummy Node
Another strategy is to use a temporary dummy node to take care of the first node case – the dummy node nothing but temporarily the first node in the list. Following is the C, Java, and Python program that demonstrates it:
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Helper function to return a new node of the linked list struct Node* newNode(int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Function to insert a given node at its correct sorted position into a given // list sorted in increasing order void sortedInsert(struct Node** head, struct Node* newNode) struct Node* current = &dummy; while (current->next != NULL && current->next->data < newNode->data) { newNode->next = current->next; int keys[] = {2, 4, 6, 8}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { sortedInsert(&head, newNode(5)); sortedInsert(&head, newNode(9)); sortedInsert(&head, newNode(1)); |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> NULL
Node(int data, Node next) // Helper function to print a given linked list public static void printList(Node head) System.out.print(ptr.data + " —> "); System.out.println("null"); // Function to insert a given node at its correct sorted position into a given // list sorted in increasing order public static Node sortedInsert(Node head, Node newNode) while (current.next != null && current.next.data < newNode.data) { newNode.next = current.next; public static void main(String[] args) int[] keys = {2, 4, 6, 8}; // points to the head node of the linked list // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); head = sortedInsert(head, new Node(5)); head = sortedInsert(head, new Node(9)); head = sortedInsert(head, new Node(1)); |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> null
def __init__(self, data=None, next=None): # Helper function to print a given linked list print(ptr.data, end=' —> ') # Function to insert a given node at its correct sorted position into a given # list sorted in increasing order def sortedInsert(head, newNode): while current.next and current.next.data < newNode.data: newNode.next = current.next if __name__ == '__main__': # points to the head node of the linked list # construct a linked list for i in reversed(range(len(keys))): head = Node(keys[i], head) head = sortedInsert(head, Node(5)) head = sortedInsert(head, Node(9)) head = sortedInsert(head, Node(1)) |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> None
3. Using Local references
Finally, we can use also use local references to insert a node into the list’s correct sorted position. The implementation can be seen below in C:
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Helper function to return a new node of the linked list struct Node* newNode(int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Function to insert a given node at its correct sorted position into a given // list sorted in increasing order void sortedInsert(struct Node** head, struct Node* newNode) struct Node** currentRef = head; while (*currentRef != NULL && (*currentRef)->data < newNode->data) { currentRef = &((*currentRef)->next); newNode->next = *currentRef; int keys[] = {2, 4, 6, 8}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { sortedInsert(&head, newNode(5)); sortedInsert(&head, newNode(9)); sortedInsert(&head, newNode(1)); |
Download Run Code
Output:
1 —> 2 —> 4 —> 5 —> 6 —> 8 —> 9 —> NULL
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list, and doesn’t require any extra space.