Linked List Operations adding node after intervals.

[akash negi]

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.

   

public static IntNode addAtIntervals(IntNode head, int interval, int value)
	{
		int counter = 0;

		
		for (int i=1; i <= length(head)-1; i++)
		{
			if (counter == interval && head.next == null)
			{

				IntNode temp2 = new IntNode();
				temp2.data = value;
				head.next = temp2;
				
				counter = 0;
				
			}
			
			else if (counter == interval)
			{
				IntNode temp = new IntNode();
				temp.data = value;
				temp.next = head.next;
				head.next = temp;
				
				counter = 0;
			}
			
			
			
			counter ++;
		}
		return head;
		
		
	}

 

Thanks!!


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

  

public static int length(IntNode head)
	{
		int counter = 1;
		
		while (head != null)
		{
			counter++;
			head = head.next;
		}
		return counter;
	}
  

[Campbell Ritchie]

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]

Thanks for replying!
Ok so I changed my algorithm to get rid of the length() completely.

 
public static IntNode addAtIntervals(IntNode head, int interval, int value)
	{
		int counter = 0;
		IntNode pointer = new IntNode();
		pointer = head;
		
			
		while (pointer != null)
		{
			if (counter == interval && pointer.next == null)// checks if the node to be added is in the end
			{

				IntNode temp2 = new IntNode();
				temp2.data = value;
				pointer.next = temp2;
				
				counter = 0;
				
			}
			
			else if (counter == interval)// will add a node in the middle of the list
			{
				IntNode temp = new IntNode();
				temp.data = value;
				temp.next = pointer.next;
				pointer.next = temp;
				
				counter = 0;
			}
			
			else
			{
				counter ++;
			}
		}
		return head;
		
		
	}

   

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]

No. Pencil and paper, as I told you earlier.

[akash negi]

done sir.. now working fine..

Thanks!

[Campbell Ritchie]

well done Please tell us how you managed it.

[akash negi]

Campbell Ritchie wrote:well done Please tell us how you managed it.

its basically the same code but I just added

 pointer = pointer.next;   

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

  IntNode temp = new IntNode();  

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!