题解 | #调整牛群顺序#

/**
 * 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) {
        // write code here
        if(n == 1){
            return head;
        }
        int sz = 0, count = 0;
        ListNode* p = head;
        //统计链表结点数目
        while(p){
            p = p->next;
            sz++;
        }
        //在原链表头结点前新增一个虚拟结点prehead
        ListNode* prehead = new ListNode(-1);
        prehead->next = head;
        p = prehead;
        //确定尾结点
        ListNode* tail = head;
        while(tail->next){
            tail = tail->next;
        }
        //确定目标结点前驱的位置
        count = sz - n;
        while(count){
            p = p->next;
            count--;
        }
        //先暂存目标结点
        ListNode* temp = p->next;
        //在链表中删除目标结点
        p->next = p->next->next;
        //将目标结点连在尾部
        tail->next = temp;
        temp->next = nullptr;
        return prehead->next;
    }
};