c# - 转换链表

Question

这是问题。

Given a linked list like a1-a2-a3-a4-b1-b2-b3-b4. Convert it into a1-b1-a2-b2-a3-b3-a4-b4.

我的算法有点低效。

1. 将链表克隆两次，结果分别是“lista”和“listb”。
2. 去掉其中一半然后使lista = a1-a2-a3-a4和listb = b1-b2-b3-b4;
3. 尝试以某种方式组合 lista 和 listb。(虽然我不知道)。

需要你的想法。

Answer 1

您可以使用 C# LinkedList 类轻松地做到这一点。

首先扫描列表以找到 b1 节点。您有另一个从 list.First 开始的变量。然后将 b1 节点移动到第一个节点之后，移动到 b2，将另一个变量移动到 a2，重复直到得到到列表的末尾。

看起来像这样:

var aNode = list.First();
var bNode = list.First();
// scan the list looking for the first `b` node.
while (!(bNode.Value[0] == 'b'))
    bNode = bNode.Next;

// now interleave the elements
while (bNode != null)
{
    var nextB = bNode.Next;
    var nextA = aNode.Next;
    list.Remove(bNode);
    list.AddAfter(aNode, bNode);
    aNode = nextA;
    bNode = nextB;
}

如果 a 节点的数量至少与 b 节点的数量相同，则上述方法将起作用。如果“b”节点比“a”节点多，则必须在每次迭代后检查 aNode 值，以确保没有走得太远。这很容易完成:

while (bNode != null && aNode.Value[0] == 'a')