题解 | #调整牛群顺序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode moveNthToEnd (ListNode head, int n) {
        // write code here
         if (head == null || n <= 1) {
            return head;
        }
         ListNode pre = new ListNode(-1); // 用于记录第倒数n+1个节点
        pre.next = head;
        ListNode left = head; // 左指针，初始时指向头节点
        ListNode right = head; // 右指针，初始时指向头节点
         
        for (int i = 0; i < n - 1; i++) {
            right = right.next; // 右指针先移动n-1步
        }
         
        while (right.next != null) {
            pre = pre.next; // 记录第倒数n+1个节点
            left = left.next; // 最后left指针到的地方就是需要移动的倒数第n个节点
            right = right.next;
        }
         
        boolean flag = true;
        if (left == head) { // 说明此时left节点发生过移动
            flag = false;
        }
         
        pre.next = left.next; // 删除倒数第n个节点
        right.next = left; // 将倒数第n个节点移动到链表末尾
        left.next = null;
         
        return flag ? head : pre.next; // 根据是否移动了头节点来返回头节点或移动后的新头节点
    }
}

题目考察的知识点：

• 链表的基本操作
• 双指针

题目解答方法：

为了找到倒数第 n 个结点，可以使用双指针的方法。首先，定义两个指针，一个快指针（fast）和一个慢指针（slow），初始时，快指针和慢指针都指向链表的头结点。

接下来，让快指针向前移动 n 步，使得快指针指向链表中的第 n+1 个结点。然后，同时移动快指针和慢指针，直到快指针指向链表的最后一个结点。

此时，慢指针指向的是要移动到末尾的结点的前一个结点。将慢指针所指结点的next指针指向慢指针的下一个结点的next指针，即跳过倒数第 n 个结点。

然后，将最后一个结点添加到链表的末尾。具体步骤如下：

1. 如果链表为空或者只有一个结点，则返回链表的头结点。
2. 创建两个指针fast和slow，并且初始化它们都指向链表的头结点。
3. 将fast指针向前移动 n 步。
4. 然后，同时移动fast指针和slow指针，直到fast指针指向链表的最后一个结点。
5. 将slow指针所指结点的next指针指向slow指针的下一个结点的next指针，即跳过倒数第 n 个结点。
6. 创建一个指针temp，并让它指向链表的头结点。
7. 遍历链表，直到temp指针指向链表的最后一个结点。
8. 将temp指针的next指针指向慢指针所指的结点，即将倒数第 n 个结点移到链表的末尾。
9. 返回链表的头结点。