在 C++ 中将单向链表转换为 XOR 链表

在本文中，我们将讨论如何在 C++ 中将单向链表转换为 XOR 链表。在深入了解其实现之前，我们将先了解单向链表和 XOR 链表。

什么是单向链表？

单向链表是一种链表，其中每个节点指向序列中的下一个节点。它没有指向前一个节点的指针。这意味着链表只能沿正向访问。

一个名为 head 的指针指向列表中的第一个项，一个尾指针指向列表中的最后一个项。

单向链表的操作包括：

• 可以在头部添加项。
• 可以在末尾插入项。
• 在列表中搜索元素。
• 在一个元素之后插入另一个元素。
• 删除末尾的项。
• 删除列表中任何位置的项。
• 可以从头部删除项。

什么是 XOR 链表？

XOR 链表是双向链表的内存高效变体，其中每个节点的 next 指针保存其前一个节点和下一个节点地址的 XOR 值。XOR 链表中的前一个和下一个节点的地址仅存储在每个节点的一个地址空间中，而双向链表将前一个和下一个列表节点（prev, next）的地址存储在每个节点的两个地址空间中。

从单向链表创建 XOR 链表的方法

• 一个 XOR 链表在每个指针中包含前一个和下一个节点地址的 XOR 值。
• 最初，我们遍历单向链表，它维护一个指向前一个节点的指针。
• 在遍历列表时，我们将通过使用 next = XOR(prev, next) 修改每个节点的 next 指针。

从单向链表创建 XOR 链表的算法

• 首先，我们需要创建 3 个节点。
• 一个 curr 节点，最初指向头部。
• 一个 prev 节点，最初指向 null。
• 一个 next 节点，最初指向 curr。
• 重复，直到 curr 为 null：
• 将 next 更新为 curr.next。
• 将 curr.next 更新为 XOR(prev, next)。
• 将 prev 更新为 curr。
• 将 curr 更新为 next。
• displayingXOR()

打印 XOR()

1. 我们将使用一个指向 NULL 的节点 prev 和一个指向头部的节点 curr 来开始 PrintingXOR 函数。
2. 我们即将打印 curr 数据。
3. 现在，我们需要后续节点的地址以进行遍历。
4. 计算方式如下：地址 (prev 节点) XOR 地址 (curr.next)。
5. 在获得下一个节点地址后，我们将把 curr 更新为下一个节点地址，并将 prev 更新为 curr。
6. 整个过程一直持续到列表末尾。

示例

让我们举一个将单向链表转换为 C++ 中的 XOR 链表的例子。

输出

说明

• 在此示例中，Node 结构中存储了数据以及前一个和下一个节点地址的 XOR 值。
• 之后，XORLinkedList 类具有用于向前遍历列表和在开头插入节点的方法。
• 为了保持 XOR 属性，insert 方法使用 XOR 操作。
• 为了获取下一个节点地址，traverseForward 方法使用 XOR 逻辑遍历列表。

时间复杂度

• 它的时间复杂度是 O(n)，因为我们只遍历列表。