求用邻接链表表示的有向图的转置

Question

算法导论22.1-3有个问题，将有向图转置（原题是邻接链表和邻接矩阵，这里只讨论邻接链表）自己写了个比较复杂，觉得不好。所以去网上找答案，看到的大多跟下面这个类似：

void Transpose(VNode Adj[], VNode newAdj[], int V)
{
    int i;
    for(i = 0; i < V; i++)
    {
        VNode *p = Adj[i].next;
        while(p != NULL)
        {
            newAdj[p->data]->next = (VNode *)malloc(sizeof(VNode));
            newAdj[p->data]->next->data = Adj[i].data;
            newAdj[p->data]->next->next = NULL;
            p = p->next;
        }
    }
}

但我感觉明显不对啊。比如原有向图的邻接链表如下

1 -> 2 ->4
2 -> 5
3 -> 6 ->5
4 -> 2
5 -> 4
6 -> 6

遍历第一个链表时，对于 1 -> 2，可以将新链表的newAdj[2]->next->data = 1; 这没问题。但是后面对于 4 -> 2，newAdj[2]->next已经指向1了，再重新分配内存并赋值为4，不就把之前的1给冲掉了吗？最后的得到的转置有向图每个链表不都最多只有两个元素了吗？

请问哪里有邻接链表转置的好的代码，最好是用c++写的，谢谢！

Answer 1

我也想要......如果你找到了,请告诉我