交换链表算法的相邻元素

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;1314     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在第 8 行设置为 B 的后继者，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 = A12     slow = slow.next.next;    // slow = C请记住，slow现在指向 C。这是接下来发生的事情：14     while (slow != null && slow.next != null) {15         Node temp = slow.next;      // temp = D16         slow.next = slow.next.next; // C.next = D.next (which is null)17         temp.next = slow;           // D.next = C18         parent.next = temp;         // A.next = D此时，节点 C 和 D 已交换，并且 A 指向 D，根据需要。该列表现在看起来像B -> A -> D -> C.循环中的最后两行只是为下次设置。请记住，现在parent指向 A。19         parent = parent.next.next;  // parent = C20         slow = slow.next;           // slow = null循环回到顶部，我们看到slow == null，所以循环退出。虽然您发布的代码有效，但它不必要地令人困惑。在进入循环之前不需要对前两个节点进行特殊交换，并且变量名称可以更具描述性。要交换两个节点，您必须将第二个点指向第一个，并将第一个指向第二个的后继节点。为此，您必须在覆盖它之前保存第二个的继任者。例如，如果你有A -> B -> C并且你想要B -> A -> C，那么你必须这样做，假设head指向 A：firstNode = head // firstNode points to AsecondNode = firstNode.next  // secondNode points to BsecondNodeSuccessor = secondNode.next // this points to CsecondNode.next = firstNode  // B now points to AfirstNode.next = secondNodeSuccessor  // A now points to Chead = 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;}注意这里的改进：我消除了前两个节点的特殊情况交换，这通过使每个交换相同来简化事情。有意义的变量名称使我所引用的节点一目了然。消除.next.next构造可以更容易地对代码进行推理，并且还可以更轻松地确定代码是否有可能取消对 null 的引用。您的调试器是一个非常有用的工具，可以帮助您了解代码的工作方式。如果您要在调试器中单步执行代码，您可以检查变量并查看每行代码如何影响状态。如果您不知道如何使用您的调试器，您现在应该花时间学习。它将为您节省数小时的调试时间，并极大地增加您对代码工作方式的理解。

Answer 2

代替交换节点，我们可以只交换数据，这很容易并且会得到所需的输出。 public Node s(Node head) {         if (head == null || head.next == null) {            return head;        }        Node temp = head;         /* Traverse only till there are atleast 2 nodes left */        while (temp != null && temp.next != null) {             /* Swap the data */            int k = temp.data;             temp.data = temp.next.data;             temp.next.data = k;             temp = temp.next.next;         }        return head;    }

Answer 3

其他两种解决方案要么不符合您的要求，要么为某些输入提供错误的结果。我提出了一个我在LeetCode 上测试过的替代方法（如果你想自己测试，请务必将 Node 类型重命名为 ListNode）。我希望我添加到代码中的注释足够清楚。如有疑问，我建议尝试在交互式调试器中执行此过程。public ListNode s(Node head) {    // if the list is empty or it's a singleton, no node needs to be swapped    if (head == null || head.next == null) {        return head;    }      // first and second are the first and second node of the current pair to swap    Node first = head;    Node second = head.next;        // parent is the node immediately before the current pair.    // Initially, there is no such pair    Node parent = null;        // the updated list starts from the second node of the first pair    head = second;        // iterate until there is a valid pair to swap    while (first != null && second != null) {        // swap the two nodes of the current pair        first.next = second.next;        second.next = first;                if (parent != null) {            // attach the second element to the updated node of the previous pair            parent.next = second;        }                // keep the invariant of parent valid: parent precedes the new pair to swap,        // if such a pair exists        parent = first;        // advance the pointers of the first and second elements of the new pair to swap        first = first.next;                    second = (first == null) ? null : first.next;    }          return head;}