反转Singly Linked List中的交替K个节点

Question

我从http://www.geeksforgeeks.org/reverse-alternate-k-nodes-in-a-singly-linked-list/

给定一个链表，编写一个函数来反转每一个交替的k个节点输入：1->2->3->4->5->6->7->8->9->NULL且k=3输出：3->2->1->4->5->6->9->8->7->NULL。

在他们的java代码中：我真的不明白为什么需要步骤2）。除kAltReverse中的第一个参数外，节点未在其他任何位置使用（节点节点，int k）方法中的此节点参数在每次递归中都被分配给一个新的变量current。然后在每个递归中使用current、prev和next变量。

那么，为什么需要步骤2）中的node.next=current呢？

 Node kAltReverse(Node node, int k) {
    Node current = node;
    Node next = null, prev = null;
    int count = 0;
    /*1) reverse first k nodes of the linked list */
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
    /* 2) Now head points to the kth node.  So change next 
     of head to (k+1)th node*/
    if (node != null) {
        node.next = current;   **// why node.next should be moved to current even though node is not impacting on anywhere else in 3), 4)???**
    }
    /* 3) We do not want to reverse next k nodes. So move the current 
     pointer to skip next k nodes */
    count = 0;
    while (count < k - 1 && current != null) {
        current = current.next;
        count++;
    }
    /* 4) Recursively call for the list starting from current->next.
     And make rest of the list as next of first node */
    if (current != null) {
        current.next = kAltReverse(current.next, k);
    }
    /* 5) prev is new head of the input list */
    return prev;
}

Answer 1

您的问题实际上与递归无关，在这种方法中，只需保留第一个prev，并将大部分代码封装在while循环中，就可以避免递归。这个问题都是关于参考资料的。

这个过程会重新排列链条。就在有问题的代码之前，您有两个未连接的链表：

3->2->1->null 4->5->...
prev node   current

设置node.next时，您正在更改节点引用的对象的特性。因此，您正在替换指向不同对象的引用。当node.next用作值时，您将获得对对象的引用。完成node.next = current后，您将获得以下内容：

3->2->1->4->5->...
prev   current
       node