Home > Applied Algorithms, Linked List > Alternative numbers and characters in Linked List problem

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!

Advertisements
  1. November 10, 2011 at 1:04 pm

    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.

  2. s
    November 21, 2011 at 10:20 am

    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

    • November 21, 2011 at 4:57 pm

      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 :

      The explanation is really inadequate..

      You can always mail me for the code. Or simply ask your doubt.

      Does it use a third pointer to store intermediate values?

      Why would you need a third pointer for “intermediate” values? I think I explained the method pretty well.

      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) ?

      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.

      How do you handle test cases? and Error checking?

      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.

      Where is code indentation and syntax highlighting?

      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.

  3. November 21, 2011 at 9:02 pm

    s is trolling, very clearly. You should feel good — only the more popular blogs get trolled. 😀

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: