题解 | #调整牛群顺序#

1. 题目考察的知识点

遍历链表以及删除链表结点，

2. 题目解答方法的文字分析

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next\textit{next}next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。 例如，在本题中，如果我们要移动节点 yyy，我们需要知道节点 yyy 的前驱节点 xxx，并将 xxx 的指针指向 yyy 的后继节点，并将yyy结点移动到尾巴结点后面。但由于头节点不存在前驱节点，因此我们需要在移动头节点时进行特殊判断。但如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。

我们首先从头节点开始对链表进行一次遍历，得到链表的长度 length。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 length-n+ 1个节点时，它就是我们需要移动的节点。但是需要注意，如果移动的节点是头节点需要做简单的判断，因为头节点的移动方式和其他的结点的移动方式有所不同。

3. 本题解析所用的编程语言

java语言

4. 完整且正确的编程代码

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) {
        if(head==null||head.next==null||n==1)
        return head;
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        int length = getLength(head);
        ListNode cur= dummy;
        //找到需要移动的结点
        for (int i = 1; i < length - n+1 ; ++i) {
            cur = cur.next;
        }
       //找到尾巴节点
        ListNode tail = head;
       while(tail.next!=null){
          tail=tail.next;
       }
         //判断移动的结点是否头节点
         if(cur==dummy){
            tail.next=head;
            head=head.next;
            tail.next.next=null;

         }else{
           tail.next=cur.next;
           cur.next = cur.next.next;
           tail.next.next=null;
         }
         
         return head;
    }
   //获取链表长度
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }


}