java中的单链表

Question

我刚刚在网上找到了这个困难的面试问题,我希望有人可以帮助我理解它.这是一个通用的问题......给定一个单链表,将列表中的每个元素成对交换,使1-> 2-> 3-> 4成为2-> 1-> 4-> 3.

您必须交换元素,而不是值.答案应该适用于循环列表,其中尾部指向列表的头部.您不必检查尾部是否指向中间(非头部)元素.

所以我认为:

public class Node
{
     public int n;     // value
     public Node next; // pointer to next node
}

实现这个的最佳方法是什么？有人可以帮忙吗？

Answer 1

我同意@Stephen 关于不给出答案（全部）的观点，但我认为我应该给你提示。

\n\n

需要理解的重要一点是，Java 没有显式指定指针 - 相反，每当将非基元（例如 not char、byte、int、double、float、long、boolean、short）传递给函数时，它都会作为引用传递。因此，您可以使用临时变量来交换值。尝试自己编写一个代码或看下面：

\n\n

 public static void swapNodeNexts(final Node n1, final Node n2) {  \n    final Node n1Next = n1.next;  \n    final Node n2Next = n2.next;  \n    n2.next = n1Next;  \n    n1.next = n2Next;  \n }  \n

\n\n

然后你需要一个数据结构来保存Nodes。重要的是有偶数个Node只有偶数个（奇数会使事情变得不必要地复杂化）。还需要初始化节点。你应该把它放在你的 main 方法中。

\n\n

  public static final int NUMPAIRS = 3;\n public static void main(final String[] args) {\n    final Node[] nodeList = new Node[NUMPAIRS * 2];\n    for (int i = 0; i < nodeList.length; i++) {\n        nodeList[i] = new Node();\n        nodeList[i].n = (i + 1) * 10;\n        // 10 20 30 40\n    }\n    // ...\n } \n

\n\n

重要的部分是设置节点的下一个值。您不能只是for对所有这些都进行循环，因为那样最后一个next会抛出一个IndexOutOfBoundsException. 尝试自己制作一个，或者看看我的。

\n\n

  for (int i = 0; i < nodeList.length - 1; i++) {\n    nodeList[i].next = nodeList[i + 1];\n }\n nodeList[nodeList.length - 1].next = nodeList[0];\n

\n\n

然后通过循环对它们运行交换函数for。但请记住，您不想在每个节点\xe2\x80\xa6 上运行它，请仔细考虑一下。

\n\n

如果你不明白，这是我的最终代码：

\n\n

 // Node\n class Node {\n    public int n; // value\n    public Node next; // pointer to next node\n\n    @Override\n    public String toString() {\n        return "Node [n=" + n + ", nextValue=" + next.n + "]";\n    }\n\n }\n\n // NodeMain\n public class NodeMain {\n    public static final int NUMPAIRS = 3;\n\n    public static void main(final String[] args) {\n        final Node[] nodeList = new Node[NUMPAIRS * 2];\n        for (int i = 0; i < nodeList.length; i++) {\n            nodeList[i] = new Node();\n            nodeList[i].n = (i + 1) * 10;\n            // 10 20 30 40\n        }\n        for (int i = 0; i < nodeList.length - 1; i++) {\n            nodeList[i].next = nodeList[i + 1];\n        }\n        nodeList[nodeList.length - 1].next = nodeList[0];\n\n        // This makes 1 -> 2 -> 3 -> 4 -> 1 etc.\n        printNodes(nodeList);\n\n        for (int i = 0; i < nodeList.length; i += 2) {\n            swapNodeNexts(nodeList[i], nodeList[i + 1]);\n        }\n\n        // Now: 2 -> 1 -> 4 -> 3 -> 1 etc.\n        printNodes(nodeList);\n\n    }\n\n    private static void printNodes(final Node[] nodeList) {\n        for (int i = 0; i < nodeList.length; i++) {\n            System.out.println("Node " + (i + 1) + ": " + nodeList[i].n\n                    + "; next: " + nodeList[i].next.n);\n        }\n        System.out.println();\n    }\n\n    private static void swapNodeNexts(final Node n1, final Node n2) {\n        final Node n1Next = n1.next;\n        final Node n2Next = n2.next;\n        n2.next = n1Next;\n        n1.next = n2Next;\n    }\n } \n

\n\n

我希望您能够在指导下至少弄清楚其中的一些内容。然而，更重要的是，理解这里的概念很重要。如果您有任何疑问，请发表评论。

\n