题解 | 调整牛群顺序 | Java

依旧考察链表遍历操作，用快慢链表去找到倒数第n个节点。

思路是让右指针先走n-1步，然后左右指针同时遍历，当右指针到最后一个节点的时候，左指针就指向了倒数第n个节点(pre)

24行是针对特殊情况的处理。

这里注意需要new一个新的节点，用于指向倒数第n+1个节点，用于节点的链接交换。

35-38其实是为了针对特殊情况的一种应对方案，即当移动第一个节点的时候，需要做的是将头节点连接到当前的尾节点后作为新的尾节点，并返回当前第二个节点作为新的头结点。所以pre要指向当前的第二个节点，并将其返回。

对于一般的情况，即交换发生在首位之间的时候，头结点不变，所以直接返回head即可。

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.next==null||n==1) return head;
        ListNode pre = new ListNode(-1), right = head, left = head;
        pre.next = head; //用于记录第倒数n+1个节点
        for(int i=0; i<n-1; i++){
            right = right.next; //右指针先移动n-1步
        }
        while(right.next!=null){
            left = left.next;//最后left指针到的地方就是需要移动的倒数第n个节点
            right = right.next;
            pre = pre.next;
        }
        boolean flag = true;
        if(left==head){ //说明此时left节点发生过移动
            flag = false;
        }
        pre.next = left.next;
        right.next = left;
        left.next = null;
        return flag? head : pre.next;
    }
}