主要观点：最近遇到一个带回家的 C 编程测试，问题是深度复制一个链表，每个节点除了常规链接外还引用链表中的随机元素，类似 LeetCode 问题 138。给出了两种解决方案，一种是通过临时修改原链表利用内存作为映射，一种是使用侵入式哈希映射且不修改原链表。
关键信息：

• 给出node结构体定义，包含next和ref指针。
• 常规链表复制简单，难的是处理ref引用。
• 第一种方案通过交错两个链表，在构造新链表时利用内存映射来解决ref问题，时间复杂度为线性，但可能无法修改原链表，如并发访问时不行。
• 第二种方案利用uintptr_t获得稳定值，通过侵入式哈希映射构建链表和哈希表，不修改原链表，时间复杂度为O(n log n)，实现简单且优雅，代码可在 gist 中获取。
  重要细节：
• 第一种方案中通过嵌套循环查找原链表中ref指向的节点，时间复杂度为二次方。
• 第二种方案中哈希表节点嵌入在链表节点前端，通过upsert函数进行查找和插入操作。循环复制时通过upsert函数轻松实现。