题解 | 调整牛群顺序

主要思路：指针

使用指针指向需要放在末尾的节点和前一节点，以及链表的末端，方便操作，具体如下图所示：

当然这只是其中一种情况，对于需要移动的节点，根据所在位置or链表长度需要分类讨论：

1. 如果链表为空，直接返回NULL；
2. 如果链表长度只有1，即只有一个节点，则直接返回原链表头head；
3. 如果需要移动的节点就是末节点，即n == 1，也只需要直接返回原链表头head；
4. 需要移动的节点是中间节点，就按照上述操作对链表指向进行更改，具体做法是:

pre节点指向cur的后一节点；

end节点指向cur节点；

cur节点指向NULL；

5. 如果需要移动的节点是头节点，那么head指针后移一位，之后操作和普通情况相同

具体C++代码如下：

/**
 * 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
        int len = 0;
        ListNode* cur = head;
        ListNode* end = NULL;

        while (cur != NULL) {
            len++;
            end = cur;
            cur = cur->next;
        }

        if (len == 0) return nullptr;
        if (len == 1 || n == 1) return head;

        cur = head;
        ListNode* pre = NULL;
        for (int i = 0; i < len - n; i++) {
            pre = cur;
            cur = cur->next;
        }
        if (cur == head) {
            head = cur->next;
        }else {
            pre->next = cur->next;
        }
        
        end->next = cur;
        cur->next = NULL;

        return head;
    }
};