题解 | #调整牛群顺序#

此题需要考虑的边界条件较多，

我们采用双指针法，和虚拟头结点

设置变量表示是否第一步结束cur就是尾结点

一开始 pre和cur都指向虚拟头结点

第一步 cur向后跳n次，此时如果cur如果是尾结点，则flag为true

第二步 cur和pre一起向后跳，直到cur的后面就是null停

此时pre指向的是目标操作节点的前一个节点， cur指向尾结点。

首先判断目标操作节点 即pre.next是不是尾结点，是的话就不用操作了，直接返回head

不是就继续操作

最后返回时根据flag判断操作节点是否是头结点来决定返回啥。

import java.util.*;

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

public class Solution {

    public ListNode moveNthToEnd (ListNode head, int n) {

        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode cur = pre;
        while (n-- > 0) {
            cur = cur.next;
        }

        boolean flag = false;
        if (cur.next == null) flag = true;

        while (cur.next != null) {
            pre = pre.next;
            cur = cur.next;
        }

        // 此时pre在操作节点的前面，cur是尾结点。
        // 操作开始
        ListNode tmp = pre.next;
        //如果该节点已经是尾结点，就不用再操作
        if (tmp.next == null)return head;
        pre.next = tmp.next;
        cur.next = tmp;
        tmp.next = null;

        // 根据flag值返回节点
        if (flag) return pre.next;
        return head;
    }
}