C语言实现两个双向链表关联连接结构的方法

核心思路是复用交叉节点，不需要额外维护链表间的映射表，直接给单个节点扩展两套独立的双向指针，分别对应横向、纵向两个维度的遍历逻辑，就能实现目标结构。

第一步：定义通用节点结构 #

每个节点同时持有两套双向指针，分别服务于两个维度的链表，非当前维度的指针直接置空即可：

// 通用节点结构
typedef struct DListNode {
    // 数据域，可根据业务替换为任意类型
    void* data;
    // 横向链表前后指针
    struct DListNode *h_prev, *h_next;
    // 纵向链表前后指针
    struct DListNode *v_prev, *v_next;
} DListNode;

结构规则很简单：

• 所有属于顶部横向主链的节点（也就是描述中的1、2、3、9），h_prev/h_next按横向顺序正确赋值，同时这些节点本身就是对应纵向链表的头节点
• 只属于纵向链表的节点（比如C、G、A、B、E），h_prev/h_next固定为NULL，只维护v_prev/v_next的指向即可

第二步：分两步完成链表连接 #

1. 先搭建横向主链表 #

按顺序创建横向主链的所有节点，只操作h_prev/h_next指针串成标准双向链表，同时把这些节点的纵向指针初始化为NULL，标记为各纵向链的起始点。
以给出的链表示例为例，横向串接逻辑为：

• 1的h_next指向2，2的h_prev指向1
• 2的h_next指向3，3的h_prev指向2
• 3的h_next指向9，9的h_prev指向3
• 横向头节点1的h_prev置NULL，横向尾节点9的h_next置NULL

2. 逐个挂载横向节点对应的纵向链表 #

对每个横向主链上的节点，从自身出发，只操作v_prev/v_next指针串接对应纵向链的其余节点即可，纵向链上的非主节点不需要赋值横向指针，保持为NULL。
以节点1对应的纵向链1>C>G为例：

• 创建C节点，将1的v_next指向C，C的v_prev指向1，C的横向双指针置NULL
• 创建G节点，将C的v_next指向G，G的v_prev指向C，G的v_next置NULL，G的横向双指针置NULL
  其余节点2对应2>A、3对应3>B、9对应9>E的挂载逻辑完全一致。

遍历规则 #

• 横向遍历整条主链时，只沿着h_prev/h_next指针移动，不会误入纵向链表
• 遍历某条纵向链时，从对应横向节点出发，只沿着v_prev/v_next指针移动，不会串到其他纵向链或横向链的其他位置
• 从任意纵向节点向上遍历到头顶点（也就是对应横向主链的节点）后，可以直接通过该节点的横向指针访问横向相邻节点，不需要额外的索引查询，定位效率为O(1)

内容的提问来源于stack exchange，提问作者Aisin Dimon