Efficient Searching according to starts with : I facing some issue with write logic for below problem.

I have two ArrayLists of strings
List1: contains huge data(Around 50 lakhs strings)

List2: will create on users input and contains some strings/characters(Ex. a,b,c,g,l,pd,sp,mta)

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

now I have to split list1 into multiple Lists according to startsWith strings in list2 
like in above case 
I need to create 8 lists as starts with '**a**', '**b**','**c**', '**g**', '**l**','**pd**', '**sp**' and '**mta**'

But the condition for above is I have to iterate List1 or List2 only once. i.e. worst complexity for algorithm should be size of List1 (50 lakhs in above case)
(Note: It is allowed to use collections.sort() method)

Can anyone please help me out around the logic.

Thanks in advance.


