题解 | #调整牛群顺序#

知识点：

1. 单链表的遍历与操作。
2. 快慢指针技巧。

题意分析：

题目描述了一个链表，表示农场里的牛，节点的值为牛的编号。农场主想要调整牛群的顺序，要求将链表中的倒数第n个节点移动到链表的末尾，并返回调整后的链表的头结点。

时间复杂度：

假设链表中有N个节点。

1. 在代码中，我们需要先找到倒数第n+1个节点，需要遍历链表一次，这需要O(N)的时间复杂度。
2. 然后，将倒数第n个节点移动到链表末尾，只需要常数时间操作，不影响时间复杂度。
3. 因此，总的时间复杂度为O(N)。

代码分析：

代码中的解决思路是使用快慢指针来定位倒数第n+1个节点和倒数第n个节点，然后将倒数第n个节点移动到链表末尾。具体的步骤如下：

1. 如果n为1，不需要移动，直接返回原链表。
2. 创建一个前置头节点preHead，方便处理边界情况。
3. 初始化快指针fast和慢指针slow，初始都指向preHead。
4. 快指针fast先向前移动N步，定位到倒数第n+1个节点。
5. 快指针fast和慢指针slow同时向前移动，直到快指针到达链表尾部。此时慢指针指向倒数第n个节点。
6. 将倒数第n个节点移动到链表末尾：先将slow.next节点删除，然后将该节点的next指针设为null，最后将fast.next指向该节点。
7. 返回移动后的链表头节点。

代码：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 将链表的倒数第N个节点移动到末尾
     *
     * @param head ListNode类 链表的头节点
     * @param n int整型 移动到末尾的倒数第N个节点
     * @return ListNode类 移动后的链表头节点
     */
    public ListNode moveNthToEnd(ListNode head, int n) {
        // 如果n为1，不需要移动，直接返回原链表
        if (n == 1) {
            return head;
        }

        // 创建一个前置头节点，方便处理边界情况
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode fast = preHead; // 快指针，用于定位倒数第N+1个节点
        ListNode slow = preHead; // 慢指针，用于定位倒数第N个节点

        // 快指针先向前移动N步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 快指针和慢指针同时向前移动，直到快指针到达链表尾部
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 此时慢指针指向倒数第N个节点，将该节点移动到链表末尾
        ListNode target = slow.next;
        slow.next = slow.next.next;
        target.next = null;
        fast.next = target;

        // 返回移动后的链表头节点
        return preHead.next;
    }
}