...
/Solution Review: Union and Intersection of Linked Lists
Solution Review: Union and Intersection of Linked Lists
This review provides a detailed analysis of solving the "Union and Intersection of Linked Lists" challenge.
We'll cover the following...
Solution: Union #
Press + to interact
main.cs
LinkedList.cs
using System;namespace chapter_3{class Challenge_9{static void Main(string[] args){LinkedList list1 = new LinkedList(); // creating listsLinkedList list = new LinkedList();var rand = new Random();int rand_num = rand.Next(5);Console.WriteLine("List 1 ");for (int i = 1; i < 5; i++){rand_num = rand.Next(5);list.InsertAtHead(rand_num); // inserting value in the list}list.PrintList();Console.WriteLine("List 2 ");for (int i = 4; i < 8; i++){rand_num = rand.Next(5);list1.InsertAtHead(rand_num); // inserting value in the list}list1.PrintList();string check = list.Union(list, list1); // calling union functionConsole.WriteLine("Union List : " + check);return;}}}
There is nothing too tricky going on here. Traverse to the tail of the first list, and link it to the first node of the second list on line 125 - 131 in LinkedList.cs. Now, remove duplicates from the combined list.
Time complexity
If you did not have the care of duplicates, the runtime complexity of this algorithm would be O(m) where m is the size of the first list. However, because of duplicates, you need to traverse the whole union list. This increases the time complexity to ...