题解 | #调整牛群顺序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* moveNthToEnd(ListNode* head, int n) {
        if (n == 1) {
            return head;
        }
 
        ListNode* preHead =new ListNode(-1);  // 相当于创建一个头节点
        preHead->next = head;
        ListNode* fast = preHead;  //记录最后一个节点
        ListNode* slow = preHead;  //记录倒数第n个位置的前一个
 
        //先走n步
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
 
        // 再一起走，直到fast到最后位置
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
 
        //交换操作
        ListNode* target = slow->next;
        slow->next = slow->next->next;
        target->next = nullptr;
        fast->next = target;
 
        return preHead->next;
    }
};