题解 | #调整牛群顺序#

知识点：

链表/寻找倒数第n个节点

分析：

首先找出倒数第 n 个结点，使用快慢指针方法。

由于我们需要找到倒数第 n个节点，因此我们可以使用两个指针同时对链表进行遍历，并且end比 prev超前 n个节点。当 end遍历到链表的末尾时，prev就恰好处于倒数第 n个节点。

具体地，初始时 end和 prev均指向头节点。我们首先使用 end对链表进行遍历，遍历的次数为 n。此时，end和prev之间间隔了 n−1 个节点，即end比prev超前了 n个节点。

在这之后，我们同时使用end和prev对链表进行遍历。当 end 遍历到链表的末尾（即 end为空指针）时，prev恰好指向倒数第 n个节点。

编程语言：

C++

完整代码：

    ListNode* moveNthToEnd(ListNode* head, int n) {
        // write code here
        if (n == 1) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = head;
        ListNode* prev = dummy,
                  * end = dummy;

        for (int i = 0; i < n; ++i) {
            end = end->next;
        }
        while (end->next) {
            prev = prev->next;
            end = end->next;
        }
        cur = prev->next;
        prev->next = cur->next;
        end->next = cur;
        cur->next = nullptr;
        return dummy->next;
    }