C#合并两个无重复列表并保留指定顺序的实现方案问询

需求回顾 #

合并两个整数列表并去重，需满足以下顺序规则：

• 两列表共有的元素，最终顺序以list2的顺序为准；
• list2独有的元素，按原顺序保留；
• list1独有的元素，插入到它们在list1中原本所在的位置对应的list2顺序位置（比如list1中在共有元素A和B之间的独有元素，要插入到结果中A之后、B之前）。

实现代码 #

using System;
using System.Collections.Generic;
using System.Linq;

public static class ListExtensions
{
    public static List<int> MergeWithCustomOrder(this List<int> list1, List<int> list2)
    {
        var list2Elements = new HashSet<int>(list2);
        var commonElements = new HashSet<int>(list1.Intersect(list2));
        var result = new List<int>();
        var addedItems = new HashSet<int>();
        
        // 存储list1独有元素的插入位置：key是list2中的元素，value是要插入到该元素之前的list1独有元素列表
        var insertBeforeMap = new Dictionary<int, List<int>>();
        int? lastCommonInList1 = null;
        var currentUniqueSegment = new List<int>();

        // 遍历list1，拆分独有元素到对应插入段
        foreach (var num in list1)
        {
            if (commonElements.Contains(num))
            {
                // 处理当前积累的独有元素段
                if (currentUniqueSegment.Any())
                {
                    if (lastCommonInList1.HasValue)
                    {
                        // 找到该段之后的共有元素，将独有元素关联到这个元素（插入到它前面）
                        if (!insertBeforeMap.ContainsKey(num))
                        {
                            insertBeforeMap[num] = new List<int>();
                        }
                        insertBeforeMap[num].AddRange(currentUniqueSegment);
                    }
                    else
                    {
                        // 独有元素段在list1的第一个共有元素之前，关联到list2的第一个元素
                        insertBeforeMap[list2.First()] = currentUniqueSegment;
                    }
                }
                lastCommonInList1 = num;
                currentUniqueSegment.Clear();
            }
            else
            {
                // 去重后加入当前段
                if (!addedItems.Contains(num))
                {
                    currentUniqueSegment.Add(num);
                    addedItems.Add(num);
                }
            }
        }

        // 处理list1末尾的独有元素段
        if (currentUniqueSegment.Any())
        {
            if (lastCommonInList1.HasValue)
            {
                // 关联到list2的最后一个元素（插入到它前面）
                var lastList2Item = list2.Last();
                if (!insertBeforeMap.ContainsKey(lastList2Item))
                {
                    insertBeforeMap[lastList2Item] = new List<int>();
                }
                insertBeforeMap[lastList2Item].AddRange(currentUniqueSegment);
            }
            else
            {
                // list1全是独有元素，直接追加到结果
                result.AddRange(currentUniqueSegment);
            }
        }

        // 遍历list2，按顺序添加元素并插入对应独有元素
        foreach (var num in list2)
        {
            if (addedItems.Contains(num))
                continue;

            // 插入关联到当前元素的list1独有元素
            if (insertBeforeMap.TryGetValue(num, out var itemsToInsert))
            {
                result.AddRange(itemsToInsert);
                insertBeforeMap.Remove(num);
            }

            result.Add(num);
            addedItems.Add(num);
        }

        // 处理剩余的插入段（比如list2为空的极端情况）
        foreach (var kvp in insertBeforeMap)
        {
            result.AddRange(kvp.Value);
        }

        return result;
    }

    // 测试示例
    public static void Main()
    {
        List<int> list1 = new List<int> { 1, 5, 12, 13, 9, 8, 14, 4, 15 };
        List<int> list2 = new List<int> { 1, 12, 6, 7, 13, 8, 9, 14, 2, 3, 15 };
        List<int> mergedList = list1.MergeWithCustomOrder(list2);
        Console.WriteLine(string.Join(", ", mergedList));
        // 输出：1, 5, 12, 6, 7, 13, 8, 9, 14, 2, 3, 4, 15
    }
}

逻辑说明 #

1. 集合预处理：用哈希集合快速判断元素归属，避免重复添加；
2. 拆分list1独有元素：遍历list1，把位于两个共有元素之间的独有元素分成段，关联到它们后面的共有元素（标记插入位置）；
3. 构建结果列表：遍历list2，每遇到一个元素，先插入关联到该元素的list1独有元素，再添加当前元素；
4. 边界处理：覆盖了list1开头/结尾全是独有元素、list2为空等极端情况，同时处理了列表自身的重复元素。

内容的提问来源于stack exchange，提问作者Happy Coconut