Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Union and Intersection of Linked Lists

Discover how to implement union and intersection operations on linked lists in C#. Learn to traverse, link, and remove duplicates, and explore the time complexity involved in these algorithms. This lesson guides you through a solution review and highlights areas for potential optimization.

We'll cover the following...

Solution: Union #

C#
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 ...