题解 | #调整牛群顺序#

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类
     */

    ListNode tail;
    int count = 0;

    public ListNode moveNthToEnd (ListNode head, int n) {
        // write code here
        ListNode ret = new ListNode(0);
        ret.next = head;

        recurr(ret, n);

        return ret.next;
    }

    public void recurr (ListNode curr, int n) {
        if (curr.next == null) {
            tail = curr;
            count++;
            return;
        }
        recurr(curr.next, n);

        count++;
        // System.out.println(curr.val + " " + count);
        if (count == n + 1) {
            tail.next = curr.next; // 5 -> 4
            curr.next = curr.next.next; // 3 -> 5
            tail.next.next = null;  // 4 -> null
        }
    }
}

瓜了，双指针可以解决的问题用了递归。。。

双指针可以以时间复杂度O(N)和空间复杂度O(1)解决，但用了递归后时间复杂度不变，但空间复杂度升至O(N)。

递归踩坑：

1. 第N个节点被移到最后一位时没把N都后一位置空，导致链表循环。
2. 头节点有可能会被移动到尾端，所以一开始就应该用虚拟节点指向头节点。