链接列表的成对交换

Question

我一直在尝试对链接列表元素进行成对交换。代替按数据交换元素，我通过交换链接来交换它们。

C# 代码：

public LinkedList pairWiseSwapLinks(LinkedList ll)
{
    LinkedList curr = ll;
    LinkedList next = curr.nextNode;
    ll = curr;
    while (curr.nextNode != null && next.nextNode != null)
    {
        curr.nextNode = next.nextNode;
        next.nextNode = curr;
        Console.WriteLine(curr.data);
        Console.WriteLine(next.data);
        curr = curr.nextNode;
        next = curr.nextNode;
        Console.WriteLine(curr.data);
        Console.WriteLine(next.data);
    }
    return ll;
}

输入为：1 -> 3 -> 10 -> 14 -> 16 -> 20 -> 40输出： 1 -> 10 -> 16 -> 40

有人可以帮助我解决我犯的错误吗？

Answer 1

有 2 个问题：

1. 在所有交换之后，您的第一个节点应该是 3 而不是您的情况下的 1，因此您应该返回原来的第二个节点（如果只有 1 怎么办？
2. 在您的情况下跳过 14 的原因是，您在每次交换中仅涉及 2 个节点作为一对。所以第一次交换后发生的事情是列表变成 3 -> 1 -> 10 -> 16 ...和 14 -> 10 -> 16，所以基本上你已经失去了 14（即你没有更改节点 1 中的"nextNode"引用，在这种情况下应该指向 14）。

我不想在这里给你直接的解决方案，但我可以给你一些提示：

1. 每次交换需要涉及 3 个节点。
2. 但是，如果只有 1/2 个节点怎么办？
3. 将所有极端情况添加到您的代码中会使它有点不可读，那么如果我在列表的头部添加一个虚拟节点，以便最终我可以只编写"return dummy.next"而不是费心查找当前的第一个节点怎么办？