Alternative numbers and characters in Linked List problem
Problem Statement: You have been given a linked list of the following form,
1 -> 2 -> 3-> a -> 4 -> b -> c -> 5 -> 6 -> d -> e -> f
You are supposed to convert it to to the form,
1 -> a -> 2 -> b -> 3 -> c -> 4 -> d -> 5 -> e -> 6 -> f
Ofcourse, the numbers and characters can be anything.
It seems to be a very simple problem to me. I am sure you would can figure out the O(n) solution for the problem as well. For those weak in linked lists, here is what you have to do.
Take 2 pointers, let us name them ALPHA and NUM. Now move ALPHA till you find an alphabet and move NUM till you find a number. Once you reach these, set your links in the required way so that the start becomes NUM -> ALPHA and move both pointers to the next nodes. Now repeat the same process.
Let us apply this in the above example,
NUM at 1, ALPHA at a, modify linked list to look like,
1 -> a -> 2 -> 3-> 4 -> b -> c -> 5 -> 6 -> d -> e -> f
NUM at 2, ALPHA at b, modify linked list to look like,
1 -> a -> 2 -> b -> 3-> 4 -> c -> 5 -> 6 -> d -> e -> f
NUM at 3, ALPHA at c, modify linked list to look list,
1 -> a -> 2 -> b -> 3-> c -> 4 -> 5 -> 6 -> d -> e -> f
Proceed in a similar fashion and you end up with the required linked list. 🙂
Bingo!
All About Algorithms 
Related problem:
You have an array with elements like [1, 2, 3, 4, 5, …, a, b, c, d, e, …] (equal number of numbers and letters, in the exact above arrangement). You have to transform it to: [1, a, 2, b, 3, c, 4, d, 5, e] in O(1) space and O(n) time.
The explanation is really inadequate..
Does it use a third pointer to store intermediate values?
Where is the formal description of the algorithms?
Where is the calculation of the complexity, or a proof of correctness perhaps (which would really be nice) ?
How do you handle test cases? and Error checking?
Where is code indentation and syntax highlighting?
Whats the use of these posts other than increasing your post count
Hi critic,
Always nice to have people like you here who understand less and find more of the faults. 🙂 Let me answer all your doubts :
You can always mail me for the code. Or simply ask your doubt.
Why would you need a third pointer for “intermediate” values? I think I explained the method pretty well.
Do you understand the method or not? Because that is the aim of this blog. To introduce the way you should solve problems. Not to give you formal descriptions, or calculate complexities. And especially not to prove the correctness. Read the “About” page and you’ll know why this blog exists. To help people with applying algorithms in problems asked during interviews.
Did I ever say I would discuss test cases? The algorithms I suggest work for all test cases. Handling trivial cases is for your coding.
Really? That is your problem? You want a formatted algorithm/code? You are welcome to go somewhere else to learn. Many people are coming here to learn everyday.
I hope I answered all your concerns. Feel free to use your real name the next time you want to comment.
s is trolling, very clearly. You should feel good — only the more popular blogs get trolled. 😀