c - Find the common nodes of two intersecting linked lists -


i asked in interview if have 2 linked list intersect in more 1 node how can find common nodes in linked list meet. find solution minimum complexity.

e.g. 

      ![linked list example][1]

linked list 1 = 11->12->13->14->15->16->17->54

linked list 2 = 23->24->13->26->14->15->35->16->45

i answered him can store addresses of 1 linked list in hashmap , compare every node's address in second list hashmap. way can achieve o(n) complexity. interviewer not satisfied.

please suggest better solution. in advance.

it can achieved in better way listen if 2 linked list intersecting @ node can traverse ones both list find length of each list move pointer of 1 list upto distance between 2 &then move both pointer simultaneouly int way whenever u node both pointers equal..

  1. given 2 singly linked list, find if intersecting. in single iteration.

    a. traverse list1 , find last element

    b. traverse list2 , find last element

    c. check if last element of list1 == last element of list2 , if equal intersecting else not

here have parsed list once :-)

  1. also find intersecting node in o(n) time , o(1) space here have asked in o(1) space need use 1 variable :-)

    a. create variable(int) diff=0

    b. parse list1 , increment diff each node

    c. parse list2 , decrement diff each node

    d. if diff > 0 list1 bigger push pointer of list1 diff times else list2 bigger push pointer of list2 mod(diff) times

    e. check if both pointers equal till reach end


Comments

Post a Comment

Popular posts from this blog

java.util.scanner - How to read and add only numbers to array from a text file -

i'm learning java , have question regarding reading file want read numbers file contains strings well. here example of file: 66.56 "3 java 3-43 5-42 2.1 1 and here coding: public class test { public static void main (string [] args){ if (0 < args.length) { file x = new file(args[0]); try{ scanner in = new scanner( new fileinputstream(x)); arraylist<double> test = new arraylist<>(); while(in.hasnext()){ if(in.hasnextdouble()){ double f=in.nextdouble(); test.add(f);} else {in.next();} } catch(ioexception e) { system.err.println("exception during reading: " + e); } } my problem add 66.56,2.1 , 1 doesn't add 3 after "3 or ignores 3-43 , 5-42 can tell me how skip strings , add doubles here? thanks all said 3 ie; "3, 3-43 , 4-42 strings either u read string , split , check number @ " , - or put in space between characters , integers. jvm after compilation tre...
Read more

rewrite - Trouble with Wordpress multiple custom querystrings -

i'm working on adding multiple querystring , doesn't seem work. i've found codes seems work others might i'm missing something. i want like: http://mydomain.com/board/?getyear=2013&getsometext2=sometext to http://mydomain.com/board/2013/sometext/ i added code below functions.php file. doesn't seem work should though. this works. echoing querystring gets both variable without problem. http://mydomain.com/board/2013/sometext/ but doesn't. tested querystring vis isset() seems nothing being set/get http://mydomain.com/board/2013/ function add_query_vars($vars) { $vars[] = "getyear"; $vars[] = "getsometext2"; return $vars; } add_filter('query_vars', 'add_query_vars'); function add_rewrite_rules($arules) { $anewrules = array('board/([^/]+)/([^/]+)/?$' => 'index.php?pagename=board&getyear=$matches[1]&getsometext2=$matches[2]'); $arules = $a...
Read more