...

/

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.

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 lists
LinkedList 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 function
Console.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 O(m+n)2O(m + n)^2 ...