交换链表算法的相邻元素

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在第 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 = 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;

}

注意这里的改进：

我消除了前两个节点的特殊情况交换，这通过使每个交换相同来简化事情。

有意义的变量名称使我所引用的节点一目了然。

消除.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;

}