edited by
1,737 views
14 votes
14 votes

Consider a linked list containing $n$ nodes, where each node contains two pointers $ptr1$ and $ptr2$. For each node, $ptr1$ points to the next node of the list. Describe how pointer $ptr2$ should be set up for each node so that you will be able to locate the $i$-th node from the start node in the list traversing no more than $[\log\: i] + [i/2]$ nodes.

edited by

2 Answers

Best answer
25 votes
25 votes

Link $1$st node's ptr2 pointer to $2$nd node. then $2$nd node to $4$th node. $4$th node to $8$th node, $8$th node to $16$th so on.

For example I need $100$th node then do like this- go to $1\rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 32 \rightarrow 64 \rightarrow 128$. Then it takes $\log i$ time.

Then to go to $100$ start at $64$ and linear traversal has to be done for $36$ times.

This linear traversal should take $i/2$ node traversals in the worst case.

Overall it would take traversing no more than $\log i + i/2 $ nodes.

edited by
0 votes
0 votes

ptr1 is pointing to next node in each node 

ptr2 if we keep like this 

  • 1st node points to 3rd node
  • 3rd node points to 5th and so on 

1->3->5->7 .... 99-> .…

Now if we want to find 100th node 

We will first go to 99th node by traversing 50 nodes and then will use ptr1 to reach 100th node total 51 traversal which is less than [log100] + [100/2]

Related questions

4 votes
4 votes
3 answers
3
12 votes
12 votes
1 answer
4
go_editor asked May 30, 2016
1,174 views
Construct a context free grammar (CFG) to generate the following language:$L = \{a^nb^mc^{n+m}: \text{n, m are integers, and } n \geq 1, m \geq 1 \}$