题解 | #调整牛群顺序#

解题思路：

        // 先获取链表的尾部，再找到链表的倒数第n个节点，并且获取它的前一个节点。

        // 1，利用前一个节点跳过该倒数第n个节点，也就是说删除该倒数第n个节点。

        // 2，把该倒数第n个节点接到链表的尾部节点后。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* moveNthToEnd(ListNode* head, int n) {
        // 先获取链表的尾部，再找到链表的倒数第n个节点，并且获取它的前一个节点。
        // 1，利用前一个节点跳过该倒数第n个节点，也就是说删除该倒数第n个节点。
        // 2，把该倒数第n个节点接到链表的尾部节点后。
        ListNode* tail = head;
        ListNode* move = head;
        ListNode* pre = nullptr;
        int sz = 1;  //用于记录链表的大小
        while(tail->next){//找尾部节点，并计算链表的大小
            tail = tail->next;
            sz++;
        }
        if(n != sz && n != 1){// 排除两个极端
            for(int i = 0; i < sz - n; i++){ //找该倒数第n个节点
                pre = move; //记录前一个节点
                move = move->next;
            }
            pre->next = move->next; // 先跳过该倒数第n个节点
            move->next = nullptr;//该倒数第n个节点是链表的尾部，因此他的下一个应置空
            tail->next = move;//接到原尾部，成为新的尾部
            return head;
        }
        else if(n == 1){ // 把尾部放到尾部，那不搞了
            return head;
        }
        else{// 头尾互换
            tail->next = new ListNode(head->val);// 直接在尾部接上一个与头节点的值相等的点；
            return head->next;// 内存污染就污染吧，不管了
        }
    }
};