1 Replies - 566 Views - Last Post: 24 April 2010 - 12:50 AM Rate Topic: -----

#1 jadawgis732  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 52
  • Joined: 04-April 09

Recursion, Linked Lists, and a Lost Soul

Posted 23 April 2010 - 07:00 PM

Okay, so I've spend the last two hours trying to figure this one out:
write a recursive method which takes two linked lists as arguments and (without any loops) returns an intersection of the two lists. I'm baffled! Here are two versions of code I came up with....please help


		IntNode commonNodes = new IntNode();
		IntNode ptr = commonNodes;
		IntNode temp2 = head2;
		IntNode temp = head1;
		if (temp.next == null) {
			if (head1.next != null) {
				if (head1.data == temp2.data) {
					commonNodes.data = temp.data;
					commonNodes = commonNodes.next;
				}
				commonNodes.next = common(head1.next, head2);
			}
		}
		if (temp2.next != null) {
			commonNodes.next = common(head1, temp2.next);
			if (head1.data == temp2.data) {
				commonNodes.data = temp.data;
				commonNodes = commonNodes.next;
			}
		}


		return commonNodes;



	public static IntNode common(IntNode head1, IntNode head2)
	{
		IntNode a = head1;
		IntNode b = head2;
		IntNode commonNodes = new IntNode();
		IntNode ptr = commonNodes;
		if (a.next != null && b.next != null) {
		if (a.data == b.data) {
		ptr.data = a.data;
		ptr = ptr.next;
		a = a.next;
		b = b.next;
		}
else if (a.data < b.data) { 
a=a.next;
}
else {
b=b.next;
}

		}
return commonNodes;

	}



Is This A Good Question/Topic? 0
  • +

Replies To: Recursion, Linked Lists, and a Lost Soul

#2 jadawgis732  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 52
  • Joined: 04-April 09

Re: Recursion, Linked Lists, and a Lost Soul

Posted 24 April 2010 - 12:50 AM

well, this is where the method stands now, I have made progress despite it not being correct. I could really use a little help
	public static IntNode common(IntNode head1, IntNode head2)
	{
		IntNode commonNodes = new IntNode();
		if (head1 == null && head2 == null) {
			System.out.print("             returned from here                ");
			return commonNodes;
		}
		if (head1.data > head2.data) {
			commonNodes = common(head1, head2.next);
			System.out.print("          head2 advance               ");
		}
		if (head1.data < head2.data) {
			commonNodes = common(head1.next, head2);
			System.out.print("            head1 advance                ");
		}
		if (head1.data == head2.data) {
			IntNode ptr = commonNodes;
			while (ptr.next != null) {
				ptr = ptr.next;
			}
			IntNode n = new IntNode();
			n.data = head2.data;
			ptr.next = n;
			System.out.print("             added a node" + head2.data + "          ");
			print(commonNodes);
			if (head1.next != null && head2.next != null) {
				commonNodes = common(head1.next, head2.next);
			}
		}
		System.out.print("             returned from there                 ");
		return commonNodes;
	}

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1