Make function that merges two lists of ints into list of tuples

Your logic can be achieved in the LINQ way.

1. listOne left join listTwo by number. Mae sure to convert listTwo as List<int?> first. This returns the result with both a and b have value or a has value.

2. Result from 1 merge (vertially) with listTwo for those listTwo's values don't exist in the result from 1.

public static List<Tuple<int?, int?>> AddPairs(List<int> listOne, List<int> listTwo)
{
    var result = (from a in listOne
            join b in listTwo.Select(x => (int?)x) on a equals b into ab
            from b in ab.DefaultIfEmpty()
            select Tuple.Create<int?, int?>(a,b)
           ).ToList();

    return result
        .Concat(listTwo.Where(x => !result.Any(y => y.Item1 == x))
               .Select(x => Tuple.Create<int?, int?>(null,x)))
        .ToList();
}

Sample .NET Fiddle

One possible approach that I find intuitive is to create three sets of as; one set for each of the three possible Tuple structures.

We know we want to create Tuples having the following structures:

1. (a, a) when both lists contain a
2. (a, null) when only the first list conatins a
3. (null, a) when only the second list contains a

To create (a, a), we need to find the items that are present in both lists.
Items that are present in both lists can be found by producing the intersection of the lists.

To create (a, null) and (null, a), we need to find items that are present in one list, but not the other.
Items that are present in exactly one of two lists can be found by producing a set difference of the two lists.

If we use System.Linq, we can

• produce the intersection of the two lists by using .Intersect(): { }.Intersect({ })
• produce a set difference of the two lists by using .Except(): { }.Except({ })

Note:
listA.Except(listB) and listB.Except(listA) will create sets containing different values; whereas listA.Intersect(listB) and listB.Intersect(listA) will create sets containing the same set of values.

I find the following implementation (returning an IEnumerable rather than a List, utilizing the yield keyword) to be quite straight-forward and easy to read:

internal static IEnumerable<Tuple<int?, int?>> PairInts(List<int?> first, List<int?> second)
{
    foreach (var match in first.Intersect(second))
    {
        yield return Tuple.Create(match, match);
    }
    
    foreach (var inFirst in first.Except(second))
    {
        yield return Tuple.Create(inFirst, (int?)null);
    }
    
    foreach (var inSecond in second.Except(first))
    {
        yield return Tuple.Create((int?)null, inSecond);
    }
}

If you need a List, it can simply be created from the result of that method:

var result = PairInts(list1, list2).ToList();

An implementation actually returning a List could look like the following:

internal static List<Tuple<int?, int?>> PairInts(List<int?> first, List<int?> second)
{
    var pairs = new List<Tuple<int?, int?>>();
    
    pairs.AddRange(first.Intersect(second)
        .Select(match => Tuple.Create(match, match)));
    
    pairs.AddRange(first.Except(second)
        .Select(inFirst => Tuple.Create(inFirst, (int?)null)));
    
    pairs.AddRange(second.Except(first)
        .Select(inSecond => Tuple.Create((int?)null, inSecond)));
    
    return pairs;
}

Here, .Select() (also from the System.Linq namespace) is being used to create a Tuple object for each item in each of the sets.

Alternatively, you could use foreach and .Add() rather than .AddRange() and .Select() by replacing:

pairs.AddRange(first.Intersect(second)
    .Select(match => Tuple.Create(match, match)));

with

foreach (var match in first.Intersect(second))
{
    pairs.Add(Tuple.Create(match, match));
}

and so on.

Example fiddle here.

This is solvable in O(nlog(n)) and O(n).

O(nlog(n))

Sort both lists. This way, you can then linearly traverse both lists checking if an element exists in both lists or not. Some pseudo-code (since I'm not fluent in C# and do not how std::tuple<> works in C++):

firstList.sort();
secondList.sort();
int firstIndex = 0, secondIndex = 0;
int firstSize = firstList.size(), secondSize = secondList.size();
List<Tuple<int?, int?>> output;

while (firstIndex < firstSize && secondIndex < secondSize) {
  if (firstList[firstIndex] < secondList[secondIndex]) {
    output.Add(firstList[firstIndex], null);
    firstIndex++;
    continue;
  }
  if (firstList[firstIndex] > secondList[secondIndex]) {
    output.Add(null, secondList[secondIndex]);
    secondIndex++;
    continue;
  }
  output.Add(firstList[firstIndex], secondList[secondIndex]);
  firstIndex++;
  secondIndex++;
}

// Now we just need to "empty" the other, potentially non-empty list.
while (firstIndex < firstSize) {
  output.Add(firstList[firstIndex++], null);
}
while (secondIndex < secondSize) {
  output.Add(null, secondList[secondIndex++]);
}

This works because every time you can instantly tell if a matching element exists in the "other" list. Simply iterate over the lists in an ascending manner, increasing either index when appropriate.

Potential problem: List may not be easy to sort, but you can linearly convert it to an array.

Also, sorting itself in this case can be done linearly via radix sort, but that's not a very elementary method. Nonetheless, this solution could technically be O(n).

O(n)

This solution involves a HashMap (it has this name in Java, in C++ it's called an unordered_map, I don't know what it's called in C#). Hashmaps provide constant-time access to keys.

First, convert both lists into hashmaps of numbers of occurences of each value. For instance, for input

[2, 2, 3], [1, 2]

you'd receive the following hasmaps

{(2, 2), (3, 1)}, {(1, 1), (2, 1)}

Then, iterate over the keys of one hashmap checking whether they exist in the other hashmap. If so, add them to the output list in the form (a,a), removing a from both hasmaps. Otherwise, add (a,null). Then, the second hashmap might not be empty so you have to iterate over the remaining elements of the other hashmap to add the elements of the form (null,a) to your output.

In this example, you'd first "see" the key 2 in the first hashmap, with a value of 2, meaning it occurred twice in the first list. The key 2 occurs with value 1 in the second hashmap, so you add (2, 2) to the output, and then add (2, null) to your output. Now, the hashmaps need to be modified to look like this:

{(3, 1)}, {(1, 1)}

Now you "see" element 3 in the first hashmap, so you add (3, null) into the output, because 3 does not occur in the second hashmap.

Lastly, you will notice that the second hashmap has a leftover element and so you add (null, 1) to your output.

internal static List<Tuple<int?, int?>> PairInts(List<int> firstList, List<int> secondList)
{
    var pairs = new List<Tuple<int?, int?>>();

    foreach (var firstItem in firstList)
    {
        var removedAnyItems = secondList.Remove(firstItem); // Try to remove any corresponding items

        pairs.Add(new Tuple<int?, int?>(firstItem, removedAnyItems ? firstItem : null)); // If removed, it will be (a, a). If it cannot be removed, it will be (a, null)
    }

    foreach (var secondItem in secondList) // Since we removed any corresponding items, this list will not have any corresponding item in first list. So it will be always (null, a)
    {
        pairs.Add(new Tuple<int?, int?>(null, secondItem));
    }

    return pairs;
}

You can use this method using LinQ namespace that is optimized.

public static List<(int?, int?)> GetPairs(List<int> list1, List<int> list2)
{
    var pairs = new List<(int?, int?)>();
    var firstNullableList = list1.ConvertAll(x => (int?)x);
    var secondNullableList = list2.ConvertAll(x => (int?)x);
    pairs = firstNullableList.ConvertAll(x => (x, secondNullableList.Find(y => y == x)));
    pairs.AddRange(secondNullableList.ConvertAll(x => (firstNullableList.Find(y => y == x), x)).Where(x => !pairs.Contains(x)));
    return pairs;
}

In terms of complexity the best possible what you can expect is O(n + m). Use HashSet to build searchable in O(1) (average) collection:

internal static List<Tuple<int?, int?>> PairInts(List<int> firstList, List<int> secondList)
{
    var hashFirst = new HashSet<int>(firstList); // O(n)
    var hashSecond = new HashSet<int>(secondList); // O(m)

    var result = new List<Tuple<int?, int?>>(firstList.Count + secondList.Count);
    
    foreach (var i in firstList)  // O(n)
    {
        int? r = i;
        int? l = null;
        if (hashSecond.Contains(i)) // O(1)
        {
            l = i;
        }

        result.Add(Tuple.Create(r, l));
    }
    
    foreach (var i in secondList)  // O(m)
    {
        int? l = i;
        if (!hashFirst.Contains(i)) // O(1)
        {
            result.Add(Tuple.Create((int?)null, l));
        }
    }

    return result;
}

Note that for small n and/or m algorithms with worse Big-O complexity can be faster.