Friday, September 16, 2011

Given pointers to two Single Linked List find out if they joined in Y shape and also at which node they are joined.

Solution:

To check whether they joined in Y shape or not --

if ( End(List1) = = End(List2) )
    // Merged

To find the node --

count1 = Size ( List1 ) ;
count2 = Size ( List2 ) ;

longList = List1 ;
smallList = List2 ;
count2 > count1 && ( swap( longList, smallList ) ) ;

for ( int i = 0; i < abs(count1 - count2); longList = longList -> next, ++i ) ;

while(longList !- null && longList != smallList )
{
      longList  =  longList -> next ;
      smallList = smallList -> next ;
}

return longList ;

In C# -

        public LinkedListNode GetIntersectionNode(LinkedList list2)
        {
            int count1 = this.Count();
            int count2 = list2.Count();

            LinkedListNode longListNode, shortListNode;
            if (count1 >= count2)
            {
                longListNode = this.Head;
                shortListNode = list2.Head;
            }
            else
            {
                longListNode = list2.Head;
                shortListNode = this.Head;
            }

            for (int i = 0; i < Math.Abs(count1 - count2); longListNode = longListNode.Next, ++i);

            while(longListNode != null && longListNode != shortListNode)
            {
                longListNode = longListNode.Next;
                shortListNode = shortListNode.Next;
            }

            return longListNode;
        }

No comments:

Post a Comment