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 != smallList )
{
      longList  =  longList -> next ;
      smallList = smallList -> next ;
}

return longList ;

No comments:

Post a Comment