Written in Java. Thanks in advance! Problem-1 Check whether a linked list is eit
ID: 3752879 • Letter: W
Question
Written in Java. Thanks in advance!
Problem-1 Check whether a linked list is either NULL-terminated or ends in a cycle (cyclic) Hints: 1. Allocate two pointers 2. Initiate both of them as head 3. One will be twice faster than other Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the list before they intersect are unknown and both the list may have it different. List1 may have nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be m n, m>n or mExplanation / Answer
//let node structure be
class Node
{
int d;
Node next;
}
//poblem 1
boolean Find_Circular(Node head)
{
//returns true if list is cyclic
//otherwise returns false
//allocating two pointers
//and intiate both to head
Node t1 = head;
Node t2 =head;//it will be twice faster than t1
if(t1!=null)//means list is not empty
while(true)
{
if(t1.next!=null)
{ t1=t1.next;
t2=t1;
}
else//means null found
{
return false;
}
//since t2 runs twice faster
//we have to move it farward again
if(t2.next!=null)
{ t2=t2.next;
}
else//means null found
{
return false;
}
if(t1==t2)//means its circular
return true;
}
//if list empty
return false;
}
//problem 2
Node Find_merge_point(Node head1,Node head2)
{
//method to find merge pont node
//and returning that merging node
//finding logic will be
//we will move forward from head of both nodes, one after another
//until a merge node is found
Node t1 = head2,t2 = head2;
int c=1;
while(t1!=t2)//upto the merge point is not found
{
if(c==1)//means first list will be moved
{
t1 =t1.next;
c=2;
}
else
{
t2=t2.next;;
c=1;
}
}
return t1;//returning merge point
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.