题解 | #调整牛群顺序#

题目考察的知识点

链表的基本操作。

题目分析

简单来说，就是调整链表中特定元素的顺序，并追加到尾部。注意这题要求的输入数`n`是倒数的数字，这里不认真看容易出错，最开始笔者以为是顺序数调整指定元素，后来才发现是倒数。那么有很多种解决方案，这里我选择的是把倒数转换为顺序数，具体做法是遍历链表得到链表的长度count，然后count-n，`+1`是因为：

然后注意一下特殊情况：

1. 当最后算出来的n为1时，说明要调整元素位置为第1个元素，此时如果长度count=1，那么说明单元素直接返回head不用处理。
2. 如果调整元素为第一个元素，在调整头指针之后记得head=cur；也就是调整头指针指向新调整的链表头指针，否则输出就是最后一个end节点。

编程语言与代码展示

编程语言使用的是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
        ListNode* cur = head;
        ListNode* end = head;
        int count = 0;
        while (cur != nullptr) {
            cur = cur->next;
            count++;//统计链表长度
        }
        cur = head;//cur 重置
        n = count - n + 1; //得到要移动的位置
        if (n == 1) { //倒数sz位置就是第一个位置
        if (count == 1) return head;//长度为1直接返回
            cur = cur->next;//记录下新头节点的位置
            head = cur;//更改head指向为新头节点
            end->next = nullptr;
            while (cur->next != nullptr) {
                cur = cur->next;
            }
            cur->next = end;
            return head;
        } else {
            while (n!=1) {//由于备注说1<=n<=sz所以不考虑数字超长度的情况
                if (n == 2) { //说明是最后一次前一次循环
                    cur = end;//记下要移动节点的前一个节点位置
                }
                end = end->next;
                n--;
            }//循环退出时的end就已经是要找的那个节点
            cur->next = end->next;//删除选中end节点
            end->next = nullptr; //隔离出来的选中end节点断开后续链表，置空方便最后链接
            while (cur->next != nullptr) {
                cur = cur->next;
            }//cur移到最后
            cur->next = end;
            return head;
        }
    }
};

总结

借这个题解总结一下常用的链表操作代码块：

//遍历链表
ListNode* cur;
while(cur != nullptr){
  //一些对链表自定义的操作...
  cur = cur->next;//链表的步进表达式，可用for
}

//寻找最后一个链表节点
while(cur->next != nullptr){
  cur = cur->next;
}//此时cur循环结束出来的时候就已经是最后一个节点的地址啦，因为结束条件是cur->next == nullptr;在单链表中这是最后一个节点的特征~

//断开某个链表节点(中间)
pre->next = cur->next;
cur->next = nullptr;//不要忘记断开后面一端连接哦！
delete cur;//如果有需要，可以释放cur这个节点的内存空间，提高内存利用率避免内存泄露

//少用二级访问cur->next->next 循环中容易段错误

经验暂时这么多，有的话后面再记录补充，任何东西不是一蹴而就的，都是一次次迭代再逐渐完善~

第一次写题解，没有描述清楚请见谅~