Programming Interview 50: Insert Value into Sorted Circular Linked List

Step by step to crack Programming Interview question 50: Insert Value into Sorted Circular Linked List

Basic Solution
1. Find a node k in the circular sorted linked list such that (n is the inserted value):

Special Cases
1. List is null
2. List contains only one node
3. Insertd value is the smaller than head
4. Inserted value is the larger than the tail

Thank you for watching.

[AI_Edu_]

That's pretty cool! My assumption here is I think each node is immutable. If each node's value is changable, your solution is perfect and that's O(1).

[edmondlebeau]

good approach. I would think differently when it comes to the encapsulation. Instead of making lists I would rather work with node structures. but both will work!

[abkyabacha]

after reading the problem I thought it looks easy and was thinking there might be some trick in it...and i found one while solving it...
u can make ur worst case (smallest element) your best case.
newNode=new Node(headNode.data);
headNode.data=newData; //smallest one
temp=head.next;
head.next=newNode;
newNode.next=temp;
Now it is a O(1) solution instead of O(N) in worst case.

[jpiilin]

Just one question though, I think there should be a head and a tail for circular list if I'm not mistaken. Good video though.

[sowmyadharg]

Seems like the dropbox links are not working. Is there any other source to get the code?

[anilapputtan]

dropboxlink for source code says "File Not Found"