题解 | #调整牛群顺序# Java

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; // 根据是否移动了头节点来返回头节点或移动后的新头节点
    }
}

该题考察的知识点包括：

1. 单链表的遍历和操作：需要对链表进行遍历，找到倒数第n个节点和链表末尾的节点，并进行节点的删除和连接操作。
2. 快慢指针：使用快慢指针的思想，快指针先移动n-1步，然后快慢指针同时移动，直到快指针到达链表末尾，找到倒数第n个节点。
3. 边界条件处理：需要注意链表为空、链表只有一个节点、n小于等于1等特殊情况的处理。
4. 链表节点的删除和连接：通过修改节点的next指针来删除节点，并通过连接节点的next指针来组织节点之间的关系。

代码解释：

• 使用pre来记录第倒数第n+1个节点，初始时指向头节点。
• 使用快慢指针的思想，右指针right先移动n-1步，然后快慢指针同时移动直到右指针到达链表末尾。此时，左指针left指向的节点就是需要移动的倒数第n个节点。
• 根据题目要求，如果移动的是头节点，则记录flag为false。
• 进行节点的删除和连接操作，最后返回头节点或者移动后的新头节点。