java - 交换链表算法的相邻元素

Question

我正在练习 java 中的链表编程问题，我对以下问题有一个可行的解决方案，但无法理解它是如何工作的。

我在每一行旁边都评论了我认为应该发生的事情，但显然我还没有掌握这些是如何工作的，有人可以解释一下我的评论在哪里是错误的以及这个解决方案是如何正确的。(在我的评论中我使用h 代表头部，s 代表慢等)

给定一个链表，交换每两个相邻节点并返回它的头。 例子: 给定 1->2->3->4，您应该将列表返回为 2->1->4->3。

public Node s(Node head) {
    // 1(h)-2-3-4 passed in
    // if only 1 node or null node return it
    if (head == null || head.next == null) {
        return head;
    }

    Node slow = head.next;   // 1h-2s-3-4
    head.next = head.next.next; // 1h-3-4
    slow.next = head; // 2s-1h-3-4
    head = slow; // 2s/h-1-3-4
    Node parent = slow.next; // 1p-3-4
    slow = slow.next.next; // 3s-4

    while (slow != null && slow.next != null) {
        Node temp = slow.next;  // 4t-null
        slow.next = slow.next.next; // 3s-null
        temp.next = slow;    // 4t-3s-null
        parent.next = temp; // 1p-4-3
        parent = parent.next.next; // 3p=null
        slow = slow.next; // 4-null, loop ends cause next to slow is null
    }
    return head; // ( head = slow from earlier) 4-null 
}

Answer 1

让我们假设一个链表 A -> B -> C -> D。

我已经对您的代码中的行进行了编号，以便于讨论。

 1 public Node s(Node head) {
 2     // if only 1 node or null node return it
 3     if (head == null || head.next == null) {
 4         return head;
 5     }
 6 
 7     Node slow = head.next;
 8     head.next = head.next.next;
 9     slow.next = head;
10     head = slow;
11     Node parent = slow.next;
12     slow = slow.next.next;
13
14     while (slow != null && slow.next != null) {
15         Node temp = slow.next;
16         slow.next = slow.next.next;
17         temp.next = slow;
18         parent.next = temp;
19         parent = parent.next.next;
20         slow = slow.next;
21     }
22     return head;
23 }

在第 7 行，slow 指向节点 B。head.next 设置为 B 的后继者，第 8 行的 C。在第 9 行，B 指向到 A，在第 10 行，head 指向 B。我的评论显示发生了什么。

 7     Node slow = head.next;      // slow = B
 8     head.next = head.next.next; // head.next = C
 9     slow.next = head;           // B.next = A (because head points to A)
10     head = slow;                // head = B

该代码交换了前两个节点。您的列表现在看起来像这样:

B -> A -> C -> D

现在代码有点困惑，主要是因为命名不当。 slow 当前指向 B。

11     Node parent = slow.next;  // parent = A
12     slow = slow.next.next;    // slow = C

请记住 slow 现在指向 C。接下来会发生什么:

14     while (slow != null && slow.next != null) {
15         Node temp = slow.next;      // temp = D
16         slow.next = slow.next.next; // C.next = D.next (which is null)
17         temp.next = slow;           // D.next = C
18         parent.next = temp;         // A.next = D

此时，节点C和D已经交换，A指向D，按要求。该列表现在看起来像 B -> A -> D -> C。

循环中的最后两行只是为下一次做准备。请记住，现在 parent 指向 A。

19         parent = parent.next.next;  // parent = C
20         slow = slow.next;           // slow = null

循环回到顶部，我们看到 slow == null，因此循环退出。

虽然您发布的代码有效，但它造成了不必要的混淆。在进入循环之前不需要对前两个节点进行特殊交换，变量名可以更具描述性。

要交换两个节点，您必须将第二个点指向第一个，将第一个指向第二个的后继节点。为此，您必须在覆盖之前保存第二个的后继者。例如，如果你有 A -> B -> C 并且你想要 B -> A -> C，那么你必须这样做，假设 head 指向 A:

firstNode = head // firstNode points to A
secondNode = firstNode.next  // secondNode points to B
secondNodeSuccessor = secondNode.next // this points to C
secondNode.next = firstNode  // B now points to A
firstNode.next = secondNodeSuccessor  // A now points to C
head = secondNode  // and head points to B

此时，secondNodeSuccessor指向C，也就是下一个firstNode。

了解如何交换节点后，您可以大大简化代码:

public Node s(Node head) {
    // if fewer than 2 nodes, return.
    if (head == null || head == null) {
        return head;
    }

    // we know that the new head will be the second node.
    Node firstNode = head;
    Node parentNode = null;

    while (firstNode != null && firstNode.next != null) {
        Node secondNode = firstNode.next;
        Node secondNodeSuccessor = secondNode.next;

        // swap the nodes
        secondNode.next = firstNode;
        firstNode.next = secondNodeSuccessor;

        if (parentNode != null) {
            // This links the previous node (the one right before
            // the two that we just swapped) to the swapped nodes.
            parentNode.next = secondNode;
        }
        // the new parent node is the last swapped node.
        parentNode = firstNode;
        firstNode = firstNode.next; // set up for next pair
    }

    return head.next;
}

注意这里的改进:

1. 我消除了前两个节点的特殊情况交换，通过使每个交换都相同来简化事情。
2. 有意义的变量名可以清楚地表明我正在引用哪个节点。
3. 消除 .next.next 构造可以更轻松地推理代码，也可以更轻松地确定代码是否可能取消引用 null。

调试器是了解代码工作方式的非常有用的工具。如果要在调试器中单步执行代码，则可以检查变量并查看每一行代码如何影响状态。如果您不知道如何使用调试器，您现在应该花时间学习。它将为您节省数小时的调试时间，并大大增加您对代码工作原理的理解。