This post is completed by 1 user

  • 1
 Add to List
Beginner

461. Insert a node in the given sorted linked list.

Objective: Given a linked list in which nodes are sorted in ascending order. Write an algorithm to insert a given node into the linked list so that all the nodes in the list will maintain the sorted order.

Example: 

Given Linked List:  -> 2, Insert node: 6
New List:  -> 2 -> 6


Given Linked List:  -> 1 -> 2 -> 4 -> 6 -> 10, Insert node: 5
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10


Given Linked List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10, Insert node: 50
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10 -> 50

Approach:

  • Base cases:
    • If the list is empty then make the new node as head of the list and return head.
    • If the head is greater than equal to the given node then add the given node at the front and make it head. Return head.
  • Iterate the list until a node is found, where current.next node > given node, insert the given node just after current node. 

Time Complexity: O(N)

Output:

Given Linked List: Linked list is Empty, Insert node: 5
New List:  -> 5
-----------------------------------------
Given Linked List:  -> 7, Insert node: 4
New List:  -> 4 -> 7
-----------------------------------------
Given Linked List:  -> 2, Insert node: 6
New List:  -> 2 -> 6
-----------------------------------------
Given Linked List:  -> 1 -> 2 -> 4 -> 6 -> 10, Insert node: 5
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10
-----------------------------------------
Given Linked List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10, Insert node: 50
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10 -> 50
-----------------------------------------

Related Problems: