[Colorific]

This is a very simple problem that I am having an issue with I'll summarize some of the code, and post the important pieces of code only ; There is a lot of it

I have this method :

public static <I extends Comparable <I> >
Node <I> union ( Node <I> ptr1, Node <I> ptr2 )

Where ptr1 represents the head of a linked list (a), and ptr2 represents the head of a linked list (.
Each head has the following elements:

   
private static class Node < N extends Comparable <N> >
{
   
public N val;
public Node <N> next; // Points to the next node

// ... more code ...

}

Linked Lists a and b have different elements stored in them. These elements are sorted, according to lexicographic ordering.

The point of the union method is to compare ptr1 and ptr2, and then determine which element belongs first. Those elements are then stored in another linked list (which will also be sorted) and returned.

int compareVal = ptr1.val.compareTo(ptr2); 

[

Since my program is using the Comparable interface, there are 3 possible outcomes:

• compareVal < 0 : Which means ptr1 belongs first. ptr1 is stored in the
  
• compareVal > 0 : Which means ptr2 belongs first.
  
• compareVal == 0 : Which means ptr1 and ptr2 are equal

I wrote the following code and it simply does not work. I think I know why - its because I'm not linking the nodes together. I kind of have an idea on how to do this, but when I actually try something, it fails...I believe my problem lies in the

tail.next = temp; 
tail = temp;

Which is overwriting everything?

public static <I extends Comparable <I> >
Node <I> union ( Node <I> ptr1, Node <I> ptr2 )
{
// A temporary Linked List that will contain all the elements from linked lists a and b, without duplicates.
Node <I> temp = new Node(null, null);

// Represents the tail of a linked list; Allows us to join two Nodes together.
Node <I> tail = new Node (null, null);

while ( (ptr1 != null) || (ptr2 != null) )
{

int compareVal = ptr1.val.compareTo(ptr2);

if ( compareVal < 0 )
{

// If there are no elements in the Linked List, then add the first element. 
// The tail will also be pointing to that element, since it is the only one in the list
if ( temp == null )
{
temp.val = ptr1.val;
temp.next = null;

tail = temp;

// Move the pointer to the next element.
ptr1 = ptr1.next;
}// end if....

// Otherwise, there is another element(s) in the list.
else
{
// ptr1 belongs first so store it in temp.
temp = new Node ( ptr1, null );

// Now point the tail, from the previous element, to the new element.
tail.next = temp;

// Now the tail should point to the new element, since it is at the end of the list.
tail = temp;

// Move ptr1 so we can compare again.
ptr1 = ptr1.next;
}// end else...

}// end if (...)

if ( compareVal > 0 )
{

// If there are no elements in the Linked List, then add the first element. 
// The tail will also be pointing to that element, since it is the only one in the list
if ( temp == null )
{
temp.val = ptr1.val;
temp.next = null;

tail = temp;

// Move the pointer to the next element.
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}// end if...

// Otherwise, there is another element(s) in the list.
else
{
// ptr2 belongs first so store it in temp.
temp = new Node ( ptr2, null );

// Now point the tail, from the previous element, to the new element.
tail.next = temp;

// Now the tail should point to the new element, since it is at the end of the list.
tail = temp;

// Move ptr2 so we can compare again.
ptr2 = ptr2.next;
}// end else...

}// end if (...)

if ( compareVal == 0 )
{

// If there are no elements in the Linked List, then add the first element. 
// The tail will also be pointing to that element, since it is the only one in the list
if ( temp == null )
{
temp.val = ptr2.val;
temp.next = null;

tail = temp;

// Move the pointer to the next element.
ptr2 = ptr2.next;
}// end if...

// ptr1 and ptr2 are equal. So only store 1 element.

temp = new Node ( ptr1, null );

// Now point the tail, from the previous element, to the new element.
tail.next = temp;

// Now the tail should point to the new element, since it is at the end of the list.
tail = temp;

// Move both pointers to the next elements.
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}// end if(...)

// ptr1 has no more elements but ptr2 does not.
if ( ptr1 == null )
{
temp = new Node (ptr2, null);

tail.next = temp;

tail = temp;

ptr2 = ptr2.next;
}

// ptr1 has no more elements but ptr2 does not.
if ( ptr2 == null )
{
temp = new Node (ptr1, null);

tail.next = temp;

tail = temp;

ptr1 = ptr1.next;
}

}// end while(...)

return temp;

}// end union(...)

// Submitted too early. Added some things.

This post has been edited by Colorific: 06 March 2009 - 02:37 PM

[pbl]

Seems a lot complicated to me:

just parse one of them and add its element to the other one

[Colorific]

pbl, on 5 Mar, 2009 - 05:46 PM, said:

Seems a lot complicated to me:

just parse one of them and add its element to the other one

Thats what I am confused on I'm pretty sure that something a) is being overwritten or two nodes are not being connected at all.

I am just having a hard time finding it because there is so much code in my program, and I am having a difficult time keeping up with everything

[BigAnt]

The link List class has an add method does it not?

And if the List is sorted just take value for each of the elements in the second list and add it to the firs list.