{"id":27675,"date":"2018-04-09T20:21:00","date_gmt":"2018-04-09T14:51:00","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27675"},"modified":"2018-09-14T18:59:05","modified_gmt":"2018-09-14T13:29:05","slug":"intersection-two-sorted-linked-lists","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/intersection-two-sorted-linked-lists\/","title":{"rendered":"Intersection of two Sorted Linked Lists"},"content":{"rendered":"

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory \u2014 the original lists should not be changed.<\/span><\/p>\n

For example, let the first linked list be 1->2->3->4->6 and second linked list be 2->4->6->8, then your function should create and return a third list as 2->4->6.<\/p>\n

Method 1 (Using Dummy Node) <\/strong>
\nThe strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either \u2018a\u2019 or \u2018b\u2019, and adding it to tail. When we are done, the result is in dummy.next.<\/div>\n
<\/div>\n
C Programming:<\/strong><\/div>\n
\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%3B%0A%20%0A%2F*This%20solution%20uses%20the%20temporary%20dummy%20to%20build%20up%20the%20result%20list%20*%2F%0Astruct%20node*%20sortedIntersect(struct%20node*%20a%2C%20struct%20node*%20b)%0A%7B%0A%20%20struct%20node%20dummy%3B%0A%20%20struct%20node*%20tail%20%3D%20%26dummy%3B%0A%20%20dummy.next%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Once%20one%20or%20the%20other%20list%20runs%20out%20\u2013%20we\u2019re%20done%20*%2F%0A%20%20while%20(a%20!%3D%20NULL%20%26%26%20b%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20if%20(a-%3Edata%20%3D%3D%20b-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20push((%26tail-%3Enext)%2C%20a-%3Edata)%3B%0A%20%20%20%20%20%20%20tail%20%3D%20tail-%3Enext%3B%0A%20%20%20%20%20%20%20a%20%3D%20a-%3Enext%3B%0A%20%20%20%20%20%20%20b%20%3D%20b-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if%20(a-%3Edata%20%3C%20b-%3Edata)%20%2F*%20advance%20the%20smaller%20list%20*%2F%20%20%20%20%20%0A%20%20%20%20%20%20%20a%20%3D%20a-%3Enext%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20b%20%3D%20b-%3Enext%3B%0A%20%20%7D%0A%20%20return(dummy.next)%3B%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20while%20(node%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%7D%0A%7D%0A%20%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20lists%20*%2F%0A%20%20struct%20node*%20a%20%3D%20NULL%3B%0A%20%20struct%20node*%20b%20%3D%20NULL%3B%0A%20%20struct%20node%20*intersect%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20the%20first%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20Created%20linked%20list%20will%20be%201-%3E2-%3E3-%3E4-%3E5-%3E6%20*%2F%0A%20%20push(%26a%2C%206)%3B%0A%20%20push(%26a%2C%205)%3B%0A%20%20push(%26a%2C%204)%3B%0A%20%20push(%26a%2C%203)%3B%0A%20%20push(%26a%2C%202)%3B%0A%20%20push(%26a%2C%201)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20the%20second%20sorted%20linked%20list%20%0A%20%20%20Created%20linked%20list%20will%20be%202-%3E4-%3E6-%3E8%20*%2F%0A%20%20push(%26b%2C%208)%3B%0A%20%20push(%26b%2C%206)%3B%0A%20%20push(%26b%2C%204)%3B%0A%20%20push(%26b%2C%202)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%2F*%20Find%20the%20intersection%20two%20linked%20lists%20*%2F%0A%20%20intersect%20%3D%20sortedIntersect(a%2C%20b)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Linked%20list%20containing%20common%20items%20of%20a%20%26%20b%20%5Cn%20%22)%3B%0A%20%20printList(intersect)%3B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20getchar()%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: O(m+n) where m and n are number of nodes in first and second linked lists respectively.<\/p>\n

Method 2 (Using Local References) <\/strong>
\nThis solution is structurally very similar to the above, but it avoids using a dummy node Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did \u2014 dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** \u201creference\u201d strategy can be used<\/p>\n

\n
C Programming:<\/strong><\/div>\n
\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%3B%0A%20%0A%2F*%20This%20solution%20uses%20the%20local%20reference%20*%2F%0Astruct%20node*%20sortedIntersect(struct%20node*%20a%2C%20struct%20node*%20b)%0A%7B%0A%20%20struct%20node*%20result%20%3D%20NULL%3B%0A%20%20struct%20node**%20lastPtrRef%20%3D%20%26result%3B%0A%20%20%0A%20%20%2F*%20Advance%20comparing%20the%20first%20nodes%20in%20both%20lists.%0A%20%20%20%20When%20one%20or%20the%20other%20list%20runs%20out%2C%20we\u2019re%20done.%20*%2F%0A%20%20while%20(a!%3DNULL%20%26%26%20b!%3DNULL)%0A%20%20%7B%0A%20%20%20%20if%20(a-%3Edata%20%3D%3D%20b-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2F*%20found%20a%20node%20for%20the%20intersection%20*%2F%0A%20%20%20%20%20%20push(lastPtrRef%2C%20a-%3Edata)%3B%0A%20%20%20%20%20%20lastPtrRef%20%3D%20%26((*lastPtrRef)-%3Enext)%3B%0A%20%20%20%20%20%20a%20%3D%20a-%3Enext%3B%0A%20%20%20%20%20%20b%20%3D%20b-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if%20(a-%3Edata%20%3C%20b-%3Edata)%0A%20%20%20%20%20%20a%3Da-%3Enext%3B%20%20%20%20%20%20%20%2F*%20advance%20the%20smaller%20list%20*%2F%20%20%20%0A%20%20%20%20else%20%20%20%0A%20%20%20%20%20%20b%3Db-%3Enext%3B%20%20%20%20%0A%20%20%7D%0A%20%20return(result)%3B%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20while(node%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%7D%0A%7D%0A%20%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20lists%20*%2F%0A%20%20struct%20node*%20a%20%3D%20NULL%3B%0A%20%20struct%20node*%20b%20%3D%20NULL%3B%0A%20%20struct%20node%20*intersect%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20the%20first%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20Created%20linked%20list%20will%20be%201-%3E2-%3E3-%3E4-%3E5-%3E6%20*%2F%0A%20%20push(%26a%2C%206)%3B%0A%20%20push(%26a%2C%205)%3B%0A%20%20push(%26a%2C%204)%3B%0A%20%20push(%26a%2C%203)%3B%0A%20%20push(%26a%2C%202)%3B%0A%20%20push(%26a%2C%201)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20the%20second%20sorted%20linked%20list%20%0A%20%20%20Created%20linked%20list%20will%20be%202-%3E4-%3E6-%3E8%20*%2F%0A%20%20push(%26b%2C%208)%3B%0A%20%20push(%26b%2C%206)%3B%0A%20%20push(%26b%2C%204)%3B%0A%20%20push(%26b%2C%202)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%2F*%20Find%20the%20intersection%20two%20linked%20lists%20*%2F%0A%20%20intersect%20%3D%20sortedIntersect(a%2C%20b)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Linked%20list%20containing%20common%20items%20of%20a%20%26%20b%20%5Cn%20%22)%3B%0A%20%20printList(intersect)%3B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20getchar()%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: O(m+n) where m and n are number of nodes in first and second linked lists respectively<\/p>\n

Method 3 (Recursive)<\/strong>
\nBelow is the recursive implementation of sortedIntersect().<\/p>\n

C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0Astruct%20node%20*sortedIntersect(struct%20node%20*a%2C%20struct%20node%20*b)%0A%7B%0A%20%20%20%20%2F*%20base%20case%20*%2F%0A%20%20%20%20if%20(a%20%3D%3D%20NULL%20%7C%7C%20b%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20If%20both%20lists%20are%20non-empty%20*%2F%0A%20%0A%20%20%20%20%2F*%20advance%20the%20smaller%20list%20and%20call%20recursively%20*%2F%0A%20%20%20%20if%20(a-%3Edata%20%3C%20b-%3Edata)%0A%20%20%20%20%20%20%20%20return%20sortedIntersect(a-%3Enext%2C%20b)%3B%0A%20%0A%20%20%20%20if%20(a-%3Edata%20%3E%20b-%3Edata)%0A%20%20%20%20%20%20%20%20return%20sortedIntersect(a%2C%20b-%3Enext)%3B%0A%20%0A%20%20%20%20%2F%2F%20Below%20lines%20are%20executed%20only%20when%20a-%3Edata%20%3D%3D%20b-%3Edata%0A%20%20%20%20struct%20node%20*temp%20%3D%20(struct%20node%20*)malloc(sizeof(struct%20node))%3B%0A%20%20%20%20temp-%3Edata%20%3D%20a-%3Edata%3B%0A%20%0A%20%20%20%20%2F*%20advance%20both%20lists%20and%20call%20recursively%20*%2F%0A%20%20%20%20temp-%3Enext%20%3D%20sortedIntersect(a-%3Enext%2C%20b-%3Enext)%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20lists%20*%2F%0A%20%20%20%20struct%20node*%20a%20%3D%20NULL%3B%0A%20%20%20%20struct%20node*%20b%20%3D%20NULL%3B%0A%20%20%20%20struct%20node%20*intersect%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Let%20us%20create%20the%20first%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20%20%20Created%20linked%20list%20will%20be%201-%3E2-%3E3-%3E4-%3E5-%3E6%20*%2F%0A%20%20%20%20push(%26a%2C%206)%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%20%20%20push(%26a%2C%204)%3B%0A%20%20%20%20push(%26a%2C%203)%3B%0A%20%20%20%20push(%26a%2C%202)%3B%0A%20%20%20%20push(%26a%2C%201)%3B%0A%20%0A%20%20%20%20%2F*%20Let%20us%20create%20the%20second%20sorted%20linked%20list%0A%20%20%20%20%20Created%20linked%20list%20will%20be%202-%3E4-%3E6-%3E8%20*%2F%0A%20%20%20%20push(%26b%2C%208)%3B%0A%20%20%20%20push(%26b%2C%206)%3B%0A%20%20%20%20push(%26b%2C%204)%3B%0A%20%20%20%20push(%26b%2C%202)%3B%0A%20%0A%20%20%20%20%2F*%20Find%20the%20intersection%20two%20linked%20lists%20*%2F%0A%20%20%20%20intersect%20%3D%20sortedIntersect(a%2C%20b)%3B%0A%20%0A%20%20%20%20printf(%22%5Cn%20Linked%20list%20containing%20common%20items%20of%20a%20%26%20b%20%5Cn%20%22)%3B%0A%20%20%20%20printList(intersect)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: O(m+n) where m and n are number of nodes in first and second linked lists respectively.<\/p>\n

<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Intersection of two Sorted Linked Lists – Linked List – Given two lists sorted in increasing order, create and return a new list representing <\/p>\n","protected":false},"author":1,"featured_media":31273,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81968,81685,81966,81687,81688,81686,81691,81694,81969,81692,81967,81690,81689],"class_list":["post-27675","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-singly-linked-list","tag-guava-intersection","tag-intersection-of-two-linked-lists-c","tag-intersection-of-two-linked-lists-java","tag-intersection-of-two-linked-lists-python","tag-intersection-of-two-lists-java","tag-intersection-of-two-sorted-linked-lists-java","tag-java-8-list-intersection","tag-java-difference-of-two-lists","tag-java-intersect-rectangle","tag-java-intersection-of-two-arrays","tag-java-list-retainall-example","tag-union-and-intersection-of-two-linked-lists-in-java","tag-union-and-intersection-of-two-linked-lists-using-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27675","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27675"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27675\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31273"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27675"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27675"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27675"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}