Answer to Question #277997 in C++ for zain

Question

Programming Problem I ( Singly Linked List)

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 lists before they intersect is unknown and may be different in each list.

For example, List 1 may have 11 nodes before it reaches the intersection point, and List 2 might have 111 nodes before it reaches the point of intersection where 111 and 11 may be m = 11, 111 < 11 or 111 > 11. Give an algorithm for finding the merging point.

Answer 1

#include<iostream>
#include<string>

using namespace std;
/*
	Algorithm
	Suppose, that we have two linked lists a and b 
	1.Find total length of two lists a.length and b.length
	2.Find which is the longer list
	3.Compare nodes of shorter list with nodes of the longer 
	and first find common nodes.
	The firs common node is the merging ponit
*/

//Make a program to realize this 

struct Node
{
	int data;
	Node* next;
	Node(int _data):data(_data){}
};

struct LinkList
{
	
	Node* head=NULL;
	//Function to count length of list
	int length()
	{
		Node* p=head;
		int i=0;
		while(p!=NULL)
		{
			p=p->next;
			i++;	
		}
		return i;
	}
	//Function to add node
	Node* AddNode(Node* temp)
	{
		if(head==NULL)
			head=temp;
		else
		{
			Node* p=head;
			while(p->next!=NULL)
			{
				p=p->next;
			}
			p->next=temp;	
		}
		return temp;	
	}
	
	//This function compare two lists and find merging point
	int mergingPoint(LinkList* pl)
	{
		int position=-1;
		if((*this).length()>pl->length())
		{
			Node* p=pl->head;
			while(p!=NULL&&position==-1)
			{
				Node* t=head;
				for(int i=0;i<(*this).length();i++)
				{
					if(p==t)
					{
						position=i;	
						break;	
					}
					t=t->next;	
				}
				p=p->next;
			}
		}
		else
		{
			Node* p=head;
			while(p!=NULL&&position==-1)
			{
				Node* t=pl->head;
				for(int i=0;i<pl->length();i++)
				{
					if(p==t)
					{
						position=i;	
						break;	
					}
					t=t->next;	
				}
				p=p->next;
			}
		}
		return position;
	}	
	void Display()
	{
		Node* p=head;
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}	
	}
};


int main()
{
	//Make two lists
	LinkList a;
	a.AddNode(new Node(3));
	a.AddNode(new Node(4));
	a.AddNode(new Node(7));
	a.AddNode(new Node(6));
	
	LinkList b;
	b.AddNode(new Node(7));
	b.AddNode(new Node(11));
	b.AddNode(new Node(23));
	b.AddNode(new Node(55));
	b.AddNode(new Node(14));
	//Imitative make an intersection Node(7)
	b.AddNode(a.head->next->next);
	cout<<"First list:\n";
	a.Display();
	cout<<endl;
	cout<<"Second list:\n";
	b.Display();
	cout<<"\nMerging point is "<<a.mergingPoint(&b);
	
}