CareerCup

here we have to parts ...
1)Given two singly linked list, find if they are intersecting. Do this in single iteration.
a) traverse list1 and find the last element
b) traverse list2 and find the last element
c) check if last element of list1 == last element of list2 , if equal intersecting else not
here we have parsed the list only once :-)

2) Also find the intersecting node in O(n) time and O(1) space
here they have asked to do it in O(1) space so we need to use only one variable :-)
a) create a variable(int) diff=0
b) parse list1 and increment diff for each node
c) parse list2 and decrement diff for each node
d)if diff is > 0 list1 is bigger so push the pointer of list1 by diff times
else list2 is bigger so push the pointer of list2 by mod(diff) times
e)Now check if both the pointers are equal till we reach end

Count size of List A, B

If one list is larger than the other, move the root of the larger list until the remaining nodes are the same.

Now, while each list.next != null, compare RootA.Next with RootB.Next. If they are equal, return true, else move RootA = RootA.Next, RootB = RootB.Next

findIntersectoin(node *p, node *q)
{
int d1=0,d2=0;
node* x=p;
while(x)
{
d1++;
x=x.next;
}
x=q;
while(x)
{
d2++;
x=x.next;
}
int d;
if(d1>d2)
{
d=d1-d2;
while(d>0)
p=p.next;

}
else
{
d=d2-d1;
while(d>0)
q=q.next;
}
while(p && q)
{
if(p.data==q.data)
return p;
p=p.next;
q=q.next;
}
return null;
}

hi,
I assume that it is a single linked list. Now If the two list is intersecting then they will have the single tail. so just go to boths tail and compare it.

How to find the point of interesection.
1) Find the length of both the list. let us say M and N.
2) now let us say M is bigger one. then find out the difference. d=M-N.
3) mow move d pointer on the bigger list.

now onward both this list has same length and they are going to merge also. So just move one node on both the list and compare nodes value. It will give u the node u are looking for.

thanks,
DD>

Just to update, keep on moving one node at a time and keep on comparing it.

Hey can two linked lists intersect? Two nodes wont have the same memory rite??

THANKX :)

Destructive solution:

[1] Scan one list, say listA and point every node until end, listA(1..n)->next to a special node called nodeIntersect.
[2] Now scan listB and see if currentNode->next==nodeIntersect. If so, currentNode of listB is the intersection point

Much less destrcutive, requiring additional space:

[1] Scan listA and add the nodes (the pointer) to a hashtable
[2] Scab listB and if any of the pointer is same in hashtable, that pointer (or the node) is the point of intersection

There must be a better solution though. I am not aware of one right now.

just move till end on both the lists. compare the addresses of the last node. O(m+n)

why is everyone assumming it's Y-shaped ? The question asks for intersection, not merging. And in that case, it could be X-shaped too.

two link list A and B..if we can modify link list then it will become quite easy task
add flag value to each node and when we traverse link list A then make flag =1 and second time when we traverse link list B if we already find flag =1 then that will be interaction point
correct me if wrong

Lets call the two lists a and b.Reverse the two lists.Continue iterating through list until a!=b.If the two lists are entirely different and they dont intersect then the return value would be false.

while(a==b){
commonNode = a;
a=a->next;
b=b->next;
count++;
}

if(a!=b && count==0){
return false;
}

else{
cout<<"List intersects at "<<commonNode->data;
return true;
}

node *temp, *prev;
temp = list_a.head;
while(temp != NULL)
{
stack_a.push(temp);
temp = temp->next;
}
temp = list_b.head;
while(temp != NULL)
{
stack_b.push(temp)
temp = temp->next;
}
prev = NULL;
temp = stack_a.pop();
while(temp == stack_b.pop())
{
prev = temp;
}
return(prev);

Pls correct me if I'm wrong.

please factor in the presence of cycles too which could throw codes into infinite loops

Say the input lists are A and B and 6 is the intersection node. Then the list looks like as below.

A==> 1->2->3->4->5->6->7->8->9->10->NULL
B==> 15->13->12->11->6->7->8->9->10->NULL

Now if you will reverse the list B then the whole list architecture will looks like as below

A==> 1-->2-->3-->4-->5-->6<--7<--8<--9<--10 <==B
NULL<--15<--13<--12<--11<--6<--7<--8<--9<--10 <==B

Now if you will try to travers list A you will get something like below

A_New==> 1-->2-->3-->4-->5-->6-->11-->12-->13-->15-->NULL

So in this A_New list, if the last node will be the same of the first node of original B list (node value 15) then we can say that there is a intersection in between list A and list B.

================================================================================

How to find the intersection node ?

say the length of list A is x, list B is y and list A_New is z. And say the length of common part of list A and B is k. (i.e k is the length from intersection node to last node).

Now we can say,

(x-k) + (y-k) = z
or, k = (x+y-z)/2

Make two stacks, one while traversing each list. Then, compare the top two elements. If they're not the same, the lists do not intersect. If they are, keep popping off both stacks until they're no longer the same. The last node that was the same on both stacks is the intersecting node.

import java.util.HashSet;
import java.util.Stack;

import simplelinkedlist.SimpleLinkedList.Node;


public class IntersectingLinkedLists2 {

	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		n1.next = n2;
		Node n3 = new Node(3);
		n2.next = n3;
		Node n4 = new Node(4);
		n3.next = n4;

		Node m1 = new Node(100);
		Node m2 = new Node(101);
		m1.next = m2;
		Node m3 = new Node(102);
		m2.next = m3;
		m3.next = n2;

		Node intersect = getIntersect(makeStack(n1), makeStack(m1));
		System.out.println("Intersection is at " + intersect.value);
		
	}
	
	public static Stack <Node> makeStack(Node n)
	{
		Stack <Node> s = new Stack();
		while(n != null)
		{
			s.push(n);
			n = n.next;
		}
		return s;
	}
	public static Node getIntersect(Stack <Node> a, Stack <Node> b)
	{
		if(a.peek() != b.peek()) 
			return null;
		else
		{
			Node intersectNode = a.peek();
			while(!a.isEmpty() && !b.isEmpty())
			{
				if(a.peek() != b.peek())
					return intersectNode;
				intersectNode = a.peek();
				a.pop();
				b.pop();
			}
			return intersectNode;
		}
	}
}

/* I m returning NULL for no common node and next node of *head1 or *head2 if common */
struct node findcommon_node(struct node *head1,struct node *head2)
{
if(*head1==NUL L&& *head2==NULL)
return NULL;
while(*head1!=NULL && *head2!=NULL)
{
if(*head1->next != *head2->next)
{
Head1=head1->next;
Head2=head2->next;
}
elseif(*head1->next !=NULL && *head2->next !=NULL)
return *head1->next ;
return NULL;
}
return NULL;
}

disregard previous one

findIntersectoin(node *p, node *q)
{
	int d1=0,d2=0;
	node* x=p;
	while(x)
	{
		d1++;
		x=x.next;
	}
	x=q;
	while(x)
	{
		d2++;
		x=x.next;
	}
	int d;
	if(d1>d2)
	{
	 	d=d1-d2;
		while(d>0)
			p=p.next;
		
	}
	else
	{
		d=d2-d1;
		while(d>0)
			q=q.next;
	}
	while(p && q)
	{
		if(p==q)
			return p;
		p=p.next;
		q=q.next;
	}
	return null;
}

If you want to do in a single scan you need to use stack. As you know 2 stack, you can use reccurssion [ correct me if I am worng ]. Following is the C++ version of the algo :
Node* intersectionPoint( Node* L1, Node* L2)
{
if( (L1 == NULL) || ( L2 == NULL))
return NULL;
Stack* stack1 = new Stack;
Stack* stack2 = new Stack;

while( (L1 != NULL) || (L2 != NULL) )
{
if( L1 != NULL )
{
stack1->push(L1);
L1 = L1->next;
}
if( L2 != NULL )
{
stack2->push(L2);
L2 = L2->next;
}

}
Node* node1, node2, prev = NULL;
while( !stack1->empty() && !stack2->empty())
{
node1 = stack1->pop();
node2 = stack2->pop();

if( node1 == node2 )
{
prev = node1; // you can keep node2 also
}
else
return prev;

}
return prev;
}

1) To find if the lists intersects scan each one till last element. If last element of list1 equals last element of list2 then they intersect. Solution involves one scan of each list.

2) To find the intersection in O(n) and O(1) I would do the following:
a) Count number of elements in each list. This can be done in O(n1+n2).
b) Traverse list#1 and while doing so - reverse it, i.e. each node now points to the previous node instead of next node. This can be done in O(n1).
c) Traverse list #2. What will happen is that once it will reach the intersection it will not "continue" to the shared nodes but will " go back" to the beginning of list #1. This can be done in O(n1+n2). Count the number of elements encountered in this scan. Refer to it as n2*

Suppose list #1 has 100 independent nodes and 20 shared nodes. and suppose list #2 has 5 independent nodes and 20 shared nodes.

The values of n1, n2 and n2* in this case will be:
n1 = 120 [ = 100 + 20]
n2 = 25 [ = 5 + 20 ]
n2' = 5 (the independent nodes) + 1 (the intersection) + 100 (the independent nodes of list 1)

What we're looking for is the number of shared nodes.
We'll get this by calculating:
(n1 + n2 - n2* -1) / 2 =
((20 + 100) + (5 + 20) - (5 + 100 + 1) - 1) / 2 = (20 + 20) / 2 = 20

All we have to do now is to start again from the last node and go back 20 nodes. This will be the intersecting node.

I hope you asked if the lists can be circular.

I think the question is not clear. Intersection does not mean inclusion. According to the question it does not have to be in "Y" shape it can be ">===<" shape. E.g. list1 = [1,2,3,4] and list2 = [0,5,2,3,6,7] so [2,3] is the intersected part and neither they end with the same node nor they start with the diff. And in this case no one can solve the problem with O(n) time and O(1) space complexity. You need to give more constraints.

Count the number of elements in two lists.
Take the difference of count.
Traverse in longer list till the difference count.
Start traversing both lists & check for common address

int main()
{

set < char > set0;
cin >> s ;
cin >> t ;

cout << s << " " << t << endl;

for (int i=0; i<strlen(s); ++i) {
set0.insert(s[i]);
}
for (i=0; i<strlen(t); ++i) {
if (set0.find(t[i]) != set0.end())
{
cout << t[i] << endl;
}
}



return 0;
}

if ( (t1->next == NULL ) || (t2->next == NULL ) )
return false;

while (t1->next != t2->next )
{ t1 = t1->next
t2 = t2->next
}
if ( (t1->next == NULL ) && (t2->next == NULL ) )
return false;
else
return true

If two singly linked lists are intersecting, the last nodes have to be the same. Just check the last nodes of both lists, you are done!

if(head1 == NULL || head2 == NULL)
	return NULL;

while(true)
{
	if(head1 == head2)
		return head1;
	
	//reached end of both list
	if(head1->next == NULL && head2->next == NULL)
		return NULL;
		
	if(head1->next != NULL)
		head1 = head1->next;
	
	if(head2->next != NULL)
		head2 = head2->next;
}

You could temporarily make one list a circular list and then do cycle detection on the other using either the tortoise and hare or Brent's algorithm. I don't see how it can be done in one iteration with constant space, unless each node already has e.g. a "visited" property but that is neither mentioned nor standard.

1. Make first list circular by connecting last->next = first, also remember first and last node and also remember total nodes in first list.
2. Now iterate through second list and at iteration check whether last and first are matched. If at any point true then lists have an intersection point. Now this solves the problem in single iteration.
3. Now problem is finding loop start point in second list. This is traditinal problem.
4. After that remove loop from first list.

boolean intersect(Node head1 , Node head2){
	Node current1 = head1;
	Node current2 = head2;
	while (current1.next != null)
		current1 = current1.next;
	while (current2.next != null)
		current2 = current2.next;
	return (current1 == current2);
}

Node intersect(Node head1 , Node head2){
	Node current1 = head1;
	Node current2 = head2;
	int d1 , d2;
	while (current1 != null){
		current1 = current1.next;
		d1++; 
	}
	while (current2 != null){
		current2 = current2.next;
		d2++;
	}
	current2 = head2;
	current1 = head1;
	while (d2 > d1){
		current2 = current2.next;
		d2--;
	}
	while (d1 > d2){
		current1 = current1.next;
		d1--;
	}
	while (current1 != null && current2 != null && current1 != current2){
		current1 = current1.next;
		current2 = current2.next;
	}
	return current1;
}

{{
bool check(node *head, node *head1)
{
if(head == NULL && head1==NULL) return false;
else if(head == NULL || head1==NULL) return false;
else
{ while(head->next !=head1->next)
{
if(head->next ==NULL || head1->next==NULL) return false;
else { head=head->next;
head1=head1->next;
}
}
return true;
}
}
}}

to find the junction of two list. The solution is:
1. traverse through list1 and mark the data in the nodes with some special value say data multiplied by -1;
2. traverse through the list2 and check if any of the nodes any negative values.
3. if so, then that node itself is junction node.

Hello ,
assume these two link list are two lines.
1. It may corss one point means Shape is "X"
2. y
3. it may not cross ") (" but about to intersect.
The ans provided is wrong.
the question is wrong - Not by value but by reference ? what does it mean.

Some "J" will ask this Q - because he him self does not know what does it mean.