Insertion in Sorted LinkedList

Perform an insertion method in sorted LinkedList.

Given sorted LinkedList as shown below.

LinkedList<int> ll1 = new LinkedList<int>();
ll1.AddLast(1);
ll1.AddLast(2);
ll1.AddLast(3);
ll1.AddLast(5);
ll1.AddLast(6);

int target = 4;

As shown above, we want to insert 4 in the ll1, while keep the linked list sorted.

The key idea is by using LinkedListNode<int>