• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Linked List Operations adding node after intervals.

 
akash negi
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all. I have my final exams coming up and I am struck on one of the practice problems..
Suppose we are given a linked list of Integers. we have to add a value after given interval..


For example, if the list is currently

9 -> 4 -> 3 -> 12 -> 4 -> 1 -> 4

and we call addAtIntervals(list, 2, 10), the list should then become

9 -> 4 -> 10 -> 3 -> 12 -> 10 -> 4 -> 1 -> 10 -> 4

because the interval is 2, we have to add 10 after every 2 nodes.


we are also given an IntNode class in which head.next represents the next element to head and head.data is equal to the value stored in the element.

Here is the code I have so far for this.. It is not working as intended.
Please have a look and let me know what looks wrong.



Thanks!!


***EDIT***
The length() function i have is as follows..

 
Campbell Ritchie
Sheriff
Posts: 48381
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you allowed for the fact that adding a node will alter the length of each node following? Also, recalculating the length after each iteration will make your method run in quadratic time.
 
akash negi
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for replying!
Ok so I changed my algorithm to get rid of the length() completely.


I am currently getting a MemoryOut error Java heap, but lets assume i will fix my memory issues, do you think it should work after that?

Thanks!!
 
Campbell Ritchie
Sheriff
Posts: 48381
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No. Pencil and paper, as I told you earlier.
 
akash negi
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
done sir.. now working fine..

Thanks!
 
Campbell Ritchie
Sheriff
Posts: 48381
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
well done Please tell us how you managed it.
 
akash negi
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:well done Please tell us how you managed it.


its basically the same code but I just added



inside the while loop. I was getting an Memory out of Bound Java heap error because it was not traversing through the list. As a result it was executing


infinite number of times and as a result the insufficient memory error..

when I added the line to the code. It works like a charm now!


thanks!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic