Archive

Posts Tagged ‘Linked List’

Tries (Overview)

January 27, 2012 1 comment

What is it? Trie? Did you mean “Tree”? No! I meant “Trie”. It is a data structure (also known as “prefix tree”) that is used in form of a dictionary. It is basically a way of representing data. I don’t think I can explain this without an example. So here we see the way to represent two words in English language using a trie. Shrey and Shayne.

As you can see, a trie gives us words with the same prefixes. In this example, “SH”. So that is how you represent words. You can do the same for numbers (in any format – binary, decimal, etc). Also, note that both have different “Y” nodes because a trie represents words on the base of prefixes. If we associate a count with each node, we can also tell the number of words starting with a particular prefix.

Please note that the insertion in a trie takes O(length) time where length is that of the word being inserted. We can create a trie for english language using a structure with information and 26 pointers for the corresponding letters. Easy, eh?

So a trie can be of many uses. In the next post, we’ll see an example of using Trie. 🙂

PS : For more information on Tries, visit http://en.wikipedia.org/wiki/Trie

PPS : Sorry for the long hiatus in posting!

Alternative numbers and characters in Linked List problem

November 10, 2011 4 comments

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!

Find the nth node from the end in a linked list.

October 22, 2011 2 comments

Today we have a very easy one in our hands. The problem statement asks you to find the nth from last node. How do you plan to do this?

Some of my friends said, “We’ll move through the whole linked list once, and calculate its length. Then we’ll start over and go to length-nth node”. Well, yeah. You can certainly do that and the time complexity will be O(n). However you are traversing the whole linked list twice which is not advisable. You can instead finish this task in one traversal of the linked list.

Can you make a guess? Well, here’s how it will be done:

Take 2 pointers both pointing at START. Now move the second pointer forward to the nth node (from start). Next, you start moving both these pointers forward by 1 node at a time. So we are maintaining a separation of n nodes between our two pointers. As soon as your second pointer reaches the end of the linked list, you can say that the first pointer is currently at the nth node from the end.

Sly, eh?! Have fun with this new algorithm! 🙂

Find the starting point of a Cycle in a Linked List.

You have been given a linked list which has a loop (or cycle) in it. You are supposed to find the starting point of this cycle. Please note that this is a singly linked list.

First of all, putting aside the matter of detecting the starting point of the loop, tell me how would you detect a loop in a linked list? This is pretty simple and you’ll love it if you haven’t heard of the solution before.

What you need to do is take 2 pointers at the start of the linked list. Now at every turn, move one of the pointers to the next position, and move the other pointer forward by 2 positions. If these pointers meet at a certain point, i.e., pointer1=pointer2, you know that there is a loop in a linked list. Otherwise, not.

Let me take an example,

In the image shown above, we take 2 pointers, point1 and point2, both pointing to node 1 (start) of the linked list.

Now at step 1, move point1 to node 2, point2 to node3

Next, move point1 to node 3, point2 to node 5

Next, move point1 to node 4, point2 to node 7

Next, move point1 to node 5, point2 to node 4 (since we move 7->8 and then 8->4 while moving 2 nodes forward)

Next, move point1 to node 6, point2 to node 6

Oh! My pointers just met! That means I have a loop in my linked list. 🙂

Now coming to the matter of finding the starting point of the loop –

When your pointers meet, you’ll be as many nodes away from the starting point of the loop as the starting of the loop is away from the start of the linked list.

This means, the start of my loop is as far from 6 as from 1. (That is true, as you can see)

To get this start of loop, put one of your 2 pointers at the start and now start moving both pointers forward by 1. When they meet, you know that this is your loop’s starting point. 🙂

Example, leave point1 at 6. Make point2 equal to start (node 1). Now moving each forward by 1,

Move point1 to node 7, point2 to node 2

Move point1 to node 8, point2 to node 3

Move point1 to node 4, point2 to node 4

They clashed! This is the start of your linked list! 😉

More questions on linked list on their way! Don’t go!

%d bloggers like this: